原题地址：https://www.lydsy.com/JudgeOnline/problem.php?id=2457

Description

       Sherry现在碰到了一个棘手的问题，有Ｎ个整数需要排序。        Sherry手头能用的工具就是若干个双端队列。        　　她需要依次处理这N个数，对于每个数，Sherry能做以下两件事： 　　1．新建一个双端队列，并将当前数作为这个队列中的唯一的数； 　　2．将当前数放入已有的队列的头之前或者尾之后。   　　对所有的数处理完成之后，Sherry将这些队列排序后就可以得到一个非降的序列。

Input

　　第一行包含一个整数N，表示整数的个数。接下来的N行每行包含一个整数D_i，其中D_i表示所需处理的整数。

Output

　　其中只包含一行，为Sherry最少需要的双端队列数。

Sample Input

　　6
　　3
　　6
　　0
　　9
　　6
　　3

Sample Output

　　2

HINT

　　100%的数据中N≤200000。

 

分析（抄的老师的题解）

　　我们会发现  正着用贪心模拟的话  可能得不到全局最优解

　　正难则反，不妨换个思路：

　　因为最后队列肯定是由几大段数字所组成的非降序列

　　就先排序，再将这一列数分成尽量少的几段，使每一段对应原题中一个合法的非降序列

　　现在我们的问题就变成了：找出每一段需要什么条件才能和原题对应

　　现在我们在原数组中找到这样一段数可以对应（即红框部分）：

　　 

　　我们发现，这样一段数，他的下标一定是单谷性质的（先递减到谷底，再递增）

　　

　　小技巧：200000是一个十分神奇的数据，这个数据需要的算法时间复杂度一般都是O(nlogn)的

　　　　　　进而可以推出用排序来做

　　　　　　[10^7及以上-->O(logn)     10^6 -->O(n)    10^5 -->O(nlogn)    10^3-->O(n²)]

 

#include<cstdio>
#include<algorithm>
using namespace std;

int n,mn[200010],mx[200010];
//mn数组 存一串数的序数中最小的那个 
//mx数组 反之 
struct AA
{
    int num,en;
}a[200010];//存题目中数组+序号 

bool cmp(AA x,AA y)//特殊的排序
{                   
    if(x.en == y.en)    
        return x.num < y.num;
    return x.en < y.en; 
}

int main()
{
    //输入
    scanf("%d",&n); 
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].en);
        a[i].num=i;
    }
    
    //按大小排序（从小到大） 
    //【高亮】大小一样的按序数从小到到大排 
    //因为后面要用到的是最小和最大序数
    //排序时将其位置固定下来 方便后续处理 
    sort(a+1,a+n+1,cmp);
    
    //预处理 把相等的一串数缩成一个数
    //只用记录其开头和末尾的序数 
    int cnt=1;
    mn[cnt]=a[1].num; 
    for(int i=2;i<=n;i++)
        if(a[i].en != a[i-1].en)
        {
            mx[cnt++]=a[i-1].num;//记录这串数字结尾 
            mn[cnt]=a[i].num;//记录下串数字开头 
            
            if(i == n)//特判一下，你就知道 
                mx[cnt]=a[n].num; 
        }
    
    //单谷判定 
    /*flag=1时即单调递减状态
      此时的k为一串数中最小的序数
      和下一串数中最大的序数比较 
      当此时的最小序数小于后一串数的最大序数
      即单调递减状态持续不下去了
      就会变成单调递减
      
      flag=0时与上面相反 
      需注意的是 
      当此时的最大序数大于后一串数的最小序数
      即单调递增状态持续不下去时（即将变成单调递减） 
      表示 这个单谷已经过去了 我们要找下一个单谷
      所以ans++ 
    */ 
    int k=0x3ffffff,flag=1,ans=1;
    for(int i=1;i<=cnt;i++)
        if(flag)
            if(k > mx[i])    k=mn[i];
            else    flag=0,k=mx[i];
        else
            if(k < mn[i])    k=mx[i];
            else    flag=1,k=mn[i],ans++;
            
    printf("%d",ans);
    
    return 0;
}