Description
Sherry现在碰到了一个棘手的问题，有Ｎ个整数需要排序。 Sherry手头能用的工具就是若干个双端队列。 她需要依次处理这N个数，对于每个数，Sherry能做以下两件事： 1．新建一个双端队列，并将当前数作为这个队列中的唯一的数； 2．将当前数放入已有的队列的头之前或者尾之后。 对所有的数处理完成之后，Sherry将这些队列排序后就可以得到一个非降的序列。
Input
第一行包含一个整数N，表示整数的个数。接下来的1行包含N个整数Di，其中Di表示所需处理的整数。
Output
其中只包含一行，为Sherry最少需要的双端队列数。
Sample Input
6 3 6 0 9 6 3
Sample Output
2
Hint
N≤200000
分析
若将输入数组a b为a将a排序后的数组 因为将队列排序后能得到单调序列，所以每一个队列为排序后都为排序后数组中连续一段 所以现在问题转化为求b中满足条件的最少划分段数
现在我们再来看怎样的划分是满足条件的 假设其中一个合法的为a[i],a[i+1]…a[j-1],a[j] 不难发现最终队列下标情况为i最小且i两边单调且单调性不同 大概是这样 就这样就行了
标程
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define SIZE 200005
using namespace std
;
struct kkk
{
int v
,num
;
bool operator < (const kkk
&other
) const
{
if(v
!= other
.v
)
return v
< other
.v
;
else
return num
< other
.num
;
}
}a
[SIZE
];
int maxa
[SIZE
],mina
[SIZE
];
int main()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
memset(maxa
,0xaf,sizeof(maxa
));
memset(mina
,0x7f,sizeof(mina
));
int n
;
scanf("%d",&n
);
for(int i
= 0;i
< n
;i
++)
scanf("%d",&a
[i
].v
),a
[i
].num
= i
;
sort(a
,a
+n
);
int nowa
= a
[0].v
,nowk
= 0;
int tot
= 0;
for(int i
= 0;i
< n
;i
++)
{
if(a
[i
].v
== nowa
)
a
[i
].v
= nowk
;
else
{
nowa
= a
[i
].v
;
nowk
++;
a
[i
].v
= nowk
;
}
}
for(int i
= 0;i
< n
;i
++)
{
maxa
[a
[i
].v
] = max(maxa
[a
[i
].v
],a
[i
].num
);
mina
[a
[i
].v
] = min(mina
[a
[i
].v
],a
[i
].num
);
}
if(nowk
== 0)
{
cout
<<1;
return 0;
}
bool flag
= true;
int tot1
= 1,tot2
= 0;
for(int i
= 1;i
<= nowk
;i
++)
{
if(flag
)
{
if(mina
[i
] < maxa
[i
-1])
flag
= false;
}
else
{
if(maxa
[i
] > mina
[i
-1])
{
flag
= true;
tot1
++;
}
}
}
if(!flag
)
tot1
++;
flag
= false;
for(int i
= 1;i
<= nowk
;i
++)
{
if(flag
)
{
if(mina
[i
] < maxa
[i
-1])
flag
= false;
}
else
{
if(maxa
[i
] > mina
[i
-1])
{
flag
= true;
tot2
++;
}
}
}
if(!flag
)
tot2
++;
cout
<<min(tot2
,tot1
);
}
