题目描述

达达现在碰到了一个棘手的问题，有$N$个整数需要排序。

达达手头能用的工具就是若干个双端队列。

她需要依次处理这$N$个数，对于每个数，达达能做以下两件事：

1．新建一个双端队列，并将当前数作为这个队列中的唯一的数；

2．将当前数放入已有的队列的头之前或者尾之后。

对所有的数处理完成之后，达达将这些队列排序后就可以得到一个非降的序列。

请你求出最少需要多少个双端序列。

输入格式
第一行输入整数$N$，代表整数的个数。

接下来$N$行，每行包括一个整数$D_i$,代表所需处理的整数。

输出格式
输出一个整数，代表最少需要的双端队列数。

数据范围
$1≤N≤200000$

样例

输入样例：
6
3
6
0
9
6
3
输出样例：
2

模拟+贪心

这道题目真的和双端队列没有什么关系.这道题目的解题思路大致如下:首先我们可以敏锐地找出两个性质.

1. 双端队列内部的所有数,一定满足单调性,也就是排好序了
2. 所有的双端队列排在一起,肯定是满足单调性,也就是也都排好序了

接着来思考,我们发现正面思考非常地难,所以我们反向思考问题,把一个$A[1,n]$的已经拍好顺序的序列,分成尽量少的段,然后每一段都是一个双端队列.

然后我们不妨,开一个数组也就是B数组,记录原数组A的每一个数的下标,然后我们发现如果B的一段满足单峰性质,也就是书上更为确切的单谷性质,那么这一段就满足条件.因为单谷性质,前半段可以视为从队头加入,后半段视为从队尾加入.单谷性质具体可以百度.

特殊情况是,如果有重复的点,也就是值相同的几个点.这个特别难以理解,个人觉得.

比较容易地理解就是,将这个值一样的点,缩点.缩成一个点就好了,反正我们只要队列的个数,不要方案,而且只要满足单调性就好,记住不是严格单调性.

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=200100;
#define pii pair<int,int>
#define fir(i,a,b) for(int i=a;i<=b;i++)
pii a[N<<1];
int cmp(pii a,pii b)
{
    return a.first==b.first ? a.second<b.second : a.first>b.first;;
}
int n,h,b,mx[N],mi[N],cnt,ans;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    fir(i,1,n)
        cin>>a[i].first,a[i].second=i;//first为值,second为下标
    sort(a+1,a+1+n,cmp);
    fir(i,1,n)
        if (a[i].first!=a[i-1].first || i==1)//缩点
        {
            mx[cnt]=a[i-1].second;
            mi[++cnt]=a[i].second;
        }
    mx[cnt]=a[n].second;
    b=true;
    h=1<<30;
    fir(i,1,cnt)
        if (!b)
        {
            if (h>mx[i])
                h=mi[i];
            else
                h=mx[i],b=true;//单调性开始变化
        }
        else
        {
            if (h<mi[i])
                h=mx[i];
            else
                h=mi[i],b=false,ans++;//单调性开始变化,同时记录值,因为当前已经抵达单谷.
        }
    cout<<ans;
    return 0;
}