题目描述

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

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

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

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

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

对所有的数处理完成之后，达达将这些队列按一定的顺序连接起来后就可以得到一个非降的序列。

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

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

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

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

数据范围
1≤N≤200000

样例

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

算法1

(模拟+贪心)

大体思路yxc大佬已经介绍的很详细了，但是yxc大佬并没有对贪心策略进行证明。
于是我研究了一下这种贪心策略，终于给出了一个比较严谨(能说服自己)的证明。限于自己的表达能力，大家凑合着看吧。

首先考虑之前的序号是递减(黑色实线)的情况

左图是值相等的序列(红色实线)中序号最大的小于之前序列的最后一个的序号的情况，这种情况的最优决策显然是让序列继续递减下去，因为如果选择让红色递增，那么红线与黑线之间一定会出现一个下凸的情况，即使右边因此避免出现出现下凸，实际下凸情况数也等于原本递减决策最坏的情况。但是如果如右图值相等的序列(红色实线)中序号最大的大于之前序列的最后一个的序号，那么无论是让值相等的序列序号递增还是递减，左边都会出现向下凸的情况（紫圈）(其实绿线左端点也可能高于黑线右端点，不影响结果)但是红色实线对应的决策右边可能会出现向下凸的情况(这里只考虑右边与该序列相邻的一个点(黑点)），因此应该选择绿色实线对应的决策。

然后考虑之前的序号是递增(黑色实线)的情况

图左不用说了，右图值相等的序列(红色实线)中序号最小的小于之前序列的最后一个的序号，那么如红色实线的决策一定会使左边出现下凸的情况，而绿色实线的决策只是可能使右边出现下凸，绿色决策即使最坏情况也只是与红色决策相等，因此选择绿色实线对应的决策。

C++ 代码

#include <bits/stdc++.h>

#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N = 2e5 + 10;
pii a[N];
vector<int> b[N];
int n;

int main() {
    cin >> n;
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        a[i] = {x, i};
    }
    sort(a + 1, a + n + 1);
    int t = 0;
    for (int i = 1; i <= n; i++) {
        b[++t].push_back(a[i].se);
        while (a[i + 1].fi == a[i].fi) {
            b[t].push_back(a[i + 1].se);
            i++;
        }
    }
    int num = INT_MAX, ans = 1;
    bool flag = false;
    for (int i = 1; i <= t; i++) {
        if (flag) {
            if (b[i][0] > num)num = b[i].back();
            else {
                ans++;
                flag = false;
                num = b[i][0];
            }
        } else {
            if (b[i].back() < num)num = b[i][0];
            else {
                flag = true;
                num = b[i].back();
            }
        }
    }
    cout << ans;
    return 0;
}