【问题描述】
Sherry现在碰到了一个棘手的问题，有Ｎ个整数需要排序。
Sherry手头能用的工具就是若干个双端队列。
她需要依次处理这N个数，对于每个数，Sherry能做以下两件事：
1．新建一个双端队列，并将当前数作为这个队列中的唯一的数；
2．将当前数放入已有的队列的头之前或者尾之后。
对所有的数处理完成之后，Sherry将这些队列排序后就可以得到一个非降的序列。
【问题分析】
加粗的字...必须要看清啊！！
因为将队列排序就可以得到一个有序的序列，所以：1.队列中是有序的 2.队列之间也是有序的
所以如果我们事先将所有数排好序，那么每个队列都是其中的一个连续的子部分，所有的队列一起组成了整个有序的序列。
那么一个子部分要能放进队列有什么要求呢？
我们在给数排序的时候，一定要带着它原来的标号走，是吧？[明显原来的顺序很重要！]
那么我们划分的时候，这些标号一定要满足先减小再增加才能放在一个双端队列里，即必须按顺序由队列的中间往两边放。
不然就会堵住？...脑洞一下就好...
然后任务就是将一个序列划分成尽量少的先减小再增加的序列[这不是直接贪心+模拟么.....]
当然还有特殊情况——相等的数。
相等的数显然可以放在一个队列中....因为我可以控制其递增或递减，于是只需要记录最大值和最小值，然后当成一个整体就好。
贪心+模拟的时候：
[配合代码看就更清楚咯...]
#include<cstdio>
#include<cstring>
#include<algorithm> using namespace std; const int maxn=; struct Node{
int x,pos;
}a[maxn]; int n,cnt,ans;
int Max[maxn],Min[maxn]; bool cmp(const Node &A,const Node &B){
if(A.x!=B.x) return A.x<B.x;
return A.pos<B.pos;
} int main(){
#ifndef ONLINE_JUDGE
freopen("2457.in","r",stdin);
#endif
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i].x),a[i].pos=i;
sort(a+,a+n+,cmp); for(int i=;i<=n;i++)
if(a[i].x!=a[i-].x || i==){
Max[cnt]=a[i-].pos;
Min[++cnt]=a[i].pos;
}
Max[cnt]=a[n].pos; int h=0x3f3f3f3f;bool b=true;
//h表示当前链末尾的 pos大小 ，b表示当前链是向上或者向下趋势。
for(int i=;i<=cnt;i++)
if(!b){
if(h>Max[i]) h=Min[i];
else h=Max[i],b=true;
}
else{
if(h<Min[i]) h=Max[i];
else ans++,h=Min[i],b=false;
} printf("%d",ans);
return ;
}