双端对列 试读

这是一篇关于蓝书的题解..因为我觉得这个题目比较好,其实蓝书的题目都挺好的,但是这个特别好,就先拿它当题解呐.
其实数据结构中的一些容器越学越会发现它的神奇之处.比如双端队列.下面是题目讲解..
题目描述:
达达现在碰到了一个棘手的问题，有N个整数需要排序。
达达手头能用的工具就是若干个双端队列。
她从1到N需要依次处理这N个数，对于每个数，达达能做以下两件事：
1．新建一个双端队列，并将当前数作为这个队列中的唯一的数；
2．将当前数放入已有的队列的头之前或者尾之后。
对所有的数处理完成之后，达达将这些队列按一定的顺序连接起来后就可以得到一个非降的序列。
请你求出最少需要多少个双端序列。
输入格式
第一行输入整数N，代表整数的个数。
接下来N行，每行包括一个整数Di,代表所需处理的整数。
输出格式
输出一个整数，代表最少需要的双端队列数。
数据范围
1≤N≤200000
输入样例：
6
3
6
0
9
6
3
输出样例：
2
咋一眼看似乎很难,无从下手.但是仔细一想,这个题目是不是就是要你把一个无序的序列变得通过双端队列使得多个连续有序最后整体有序?也就是说一个双端队列存的数一定是连续有序的.我们来想一下假如连续数的id是3 5 2那一个双端队列可以存下吗?答案肯定是不可以的.因为我们必先处理2然后处理3最后处理5,处理5的时候2 3连在一起了.所以不符合标准.但5 3 4是可以的，所以我们很容易就发现一个双端队列存储的图是如下的:

中间那个值最小,两边可以连续变大.
假如数据中不存在相同的元素,似乎答案就很简单了,我们令开始点的上个点为最高点,一旦发现出现过if(a[i]<a[i+1]) flag=1;
且if(flag&&a[i]>a[i+1])则 cnt++;对吧?把图像转化为代码就是上面那些.
但是根据上面的样例知道肯定有重复数据,那么重复数据该如何处理呢? 其实也很简单,贪心一下就好了.我们知道双端队列能存的数据一定是图中那样的吧?我们把重复的尽量维持它原有的形状便是最有了,而后面假如存不下的只能再开个双端队列了,保持递减的顺序,也就是说,假如我现在可以用已经开的双端队列全部存下,我就存下,存不下就只能重新开个双端队列了.我还是用图来解释下这两种情况.
注意图中第一条线是之前数构成的形状,而第二条线是当前相同数的一个id范围.升序降序任意排,主要是尽量维护之前的形状.
代码:

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct node{
   int id,v;  
}a[N];
bool cmp(node l,node r)
{
    if(l.v==r.v) return l.id<r.id;
    else return  l.v<r.v;
}
int main()
{
    int n,cnt=1;
    cin>>n;
    for(int i=1;i<=n;i++) { scanf("%d",&a[i].v);a[i].id=i; }
    sort(a+1,a+1+n,cmp);
    a[0].id=123123123;int flag=-1;//-1表示下降,1表示上升
    for(int i=1;i<=n;i++) 
    {
        int j=i+1;
        while(a[i].v==a[j].v) j++;
        int mi=a[i].id; int mx=a[j-1].id;
        if(flag==1)//上升
        {
            if(a[i-1].id>mi)  { cnt++;flag=-1;a[j-1]=a[i];i=j-1; }
            else i=j-1;
        }
        else if(flag==-1)//下降
        {
            if(a[i-1].id<mx)  { flag=1;i=j-1; }
            else { a[j-1]=a[i];i=j-1; }
        }
    }
    cout<<cnt<<endl;
    return 0;
}