题解：P10465 双端队列

· · 题解

题意

  1. 你有一个序列，里面有若干个数，你同时拥有若干个双端队列。
  2. 你需要从前往后遍历每一个元素，对于每一个元素，你可选择一个双端队列，从前插入或从后插入。
  3. 我们希望所有元素插入之后，所有双端队列顺次连接，构成一个单调不减的序列。
  4. 请问所需要双端序列的最小值。

思路

窥得一隅

如果用最坏的方法，双端序列的个数等于元素个数，但是我们可以考虑合并。 考虑能否只用 1 个双端序列，很明显，有一个数 x 要插入队列 q，如果 x\le q_1，则 x 可以插入队头，如果 x\ge q_m，则 x 可以插入队尾。

显然这是对的，但是如果我们有一个 x\in (q_1,q_m)，就无法插入队头或者队尾了，但是我们最后需要一个单调不减的序列，所以很多情况下，1 个双端队列不足以通过队头和队尾的插入来构建一个单调不减的序列。

那我们怎么办呢？

渐入佳境

虽然我们发现直接输出 1 是错的，但是在刚刚那个错误的思路中，我们知道了元素插入双端队列的方式，也知道了问题，但是我们换一个角度，如果我们有 k 个双端队列，那么，在我们插入的时候，对于每一个双端队列，是不是就是通过和队尾与队头的比较来插入，所以每个队列内部同样也是单调不减的 废话，这个时候，我们就可以观察队列内部的元素在原始序列的编号有什么规律。

多次模拟后，不难发现，队列内部的标号呈现单谷的样子，其中又有什么奥妙呢？

可以假定，在最终的某个双端队列 q 中，它最初的元素在第 k 位，而 q_k 表示这个元素的编号。

因为最初的元素是 k 位，所以显然的，q_k 是双端队列 q 中的最小值，考虑剩下的数以及下标 i：

  1. 考虑 \forall i \in (k, m]，因为 q_i 比 q_{i-1} 更后进入双端队列，所以 q_i > q_{i-1}。
  2. 反之亦然。

所以，每个队列中是呈现单谷状的。

结论

既然每个队列中，每个元素的编号的排列是呈现单谷状的，而所有队列合并在一起等价于排序后的原序列，那么我们可以利用多关键字排序，考虑在排序后的原序列中，以每个元素原本的位置绘成函数图像，计算图像中有多少个区间内部是呈单谷状的，就是答案。

代码

结论可能有点小抽象，看一下代码（码风有点丑）。

#include <bits/stdc++.h>
#define upp(a,x,y) for (int a=x;a<=y;a++)
#define dww(a,x,y) for (int a=x;a>=y;a--)
#define pb(x) push_back(x)
#define endl '\n'
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N=200010;
int n;
PII a[N];
int main(){
    cin>>n;
    upp(i,0,n-1)
    {
        cin>>a[i].x;
        a[i].y=i;
    }
    sort(a,a+n);
    int res=1,last=INT_MAX,dir=-1;
    int i=0;
    while (i<n)
    {
        int j=i;
        while (j<n&&a[j].x==a[i].x) j++;
        int minp=a[i].y,maxp=a[j-1].y;
        if (dir==-1)
        {
            if (last>maxp) last=minp;
            else dir=1,last=maxp;
        }
        else
        {
            if (last<minp) last=maxp;
            else dir=-1,last=minp,res++;
        }
        i=j;
    }
    cout<<res;
    return 0;
}

完结撒花！！！