题解：P10465 双端队列

· · 题解

Solution

因为一定有一个分界点是第一个进入新队列的，在整个队列中位于 a 的位置一定是最前的，而分界点左边的数在 a 中一定是由前到后的顺序，分界点右边同理。所以我们发现了性质。

性质： 双端队列中的数一定在 a 中的位置（即数组 a 中的下标号）呈单谷。（先下降在上升）这意味着，只要满足一个数列在 a 中的位置呈单谷，就一定可以用题目中的操作，构造一个这样的双端队列。

接着由于是要求组合后的队列非严格单调递增，所以先将序列排序。如果考虑对于原序列进行划分，那么会发现很困难。所以考虑对排序的序列划分。那么就是把排序的序列分成几段，使得每个序列从左到右的数在 a 中的位置呈单谷。

如果有了重复的数，就会使得重复的数在 a 中的位置可以是任意一个与其相同的数的位置。

其实重复的数就相当于在排好序的数组中，我们可以任意改变重复数那一段每个数 a 中位置的顺序。

假如目前的队列是在下降的，如果这一段数在 a 中的最大位置小于队列的上个数，那我们就可以直接加入这一段，队列的最后一个数为最小数。如果不是，我们就认定队列开始上升了，队列的最后一个数为最大数。

假如我们目前的队列是在上升的，如果这一段数在 a 中的最小位置大于队列的上个数，那我们就可以加入这一段而不增加一个队列，队列的最后一个数为最大数，否则我们就需要增加一个队列，并重新开始下降。队列的最后一个数为最小数。

我们这样安排重复的数在 a 中的位置，使整体的变化上升下降次数最少，就可以得到需要的最少的队列数了，因为实际上使整体的变化上升下降次数最少的方案是可以包括那些不在策略中的上升或下降的不使目前答案变大的方案的，而使答案变大的方案，就浪费了队列，所以不可能优。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
pair<int,int> a[N];
int ans,n;
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].first,a[i].second=i;sort(a+1,a+1+n);
    ans=1;//先有一段 
    for(int i=1,value=-1,last=0x3f3f3f3f;i<=n;i++)
    {
        int j=i;
        while(j+1<=n&&a[i].first==a[j+1].first) j++;
        /*  pair<int,int> sort
            if(a[i].first==a[i+1].first)
              a[i].second<a[i+1].second  */
        if(value==-1)
            if(a[j].second<last) last=a[i].second;
            else value=1,last=a[j].second;
        else
            if(a[i].second>last) last=a[j].second;
            else ans++,value=-1,last=a[i].second;
        i=j;
        //i++;
    }
    cout<<ans;
    return 0;
}