贪心

贪心

问题一：怎么使用双端队列排序？

我们需要把一段没有排序的数字输入到双端队列中并且排好序了，怎么操作呢

1. 首先插入第一个数字
2. 后续数字如果比队尾数字大，就从后边插入
3. 如果比队头元素小，就从前面插入
4. 除此之外，如果它即比队头大，又比队尾小，那么这个队列不能将他排序，需要在开一个队列

后面插入的下标都会更大，第一个数的下标为1

结论：用双端队列排好序后，里面数的下标呈现 单谷性质（先单调递减，后单调递增）

所以说：

第一：我们先将序列排好序，观察他们的坐标，他们的坐标呈现几个单谷，就需要几个双端队列

第二：排好序后， 值一样的数可以相互交换下标，这样并不影响这个有序的序列

问题转化为：我们如何操作，使谷峰最少？

先找到值一样的数里面，下标的最大最小值maxv，minv；

基于以上贪心思路，可以使波谷出现次数最少。

if(st == -1)                                    //初始为下降状态
        {
            if(maxv < last) last = minv;        //第一种
            else 
            {
                st = 1;
                last = maxv;                    //第二种
            }
        }
        else
        {
            if(last < minv) last = maxv;        //第三种
            else
            {
                res ++ ;
                last = minv;                    //第四种
                st = -1;
            }
        }

AC

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10;

int n;
PII a[N];

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++ )
    {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a, a + n);
    
    int res = 1;
    int last = n + 1;
    int st = -1;
    int i = 0;
    while(i < n)
    {
        int j = i;
        while(j < n && a[j].first == a[i].first) j ++ ;
        
        int minv = a[i].second;
        int maxv = a[j - 1].second;
        if(st == -1)
        {
            if(maxv < last) last = minv;
            else 
            {
                st = 1;
                last = maxv;
            }
        }
        else
        {
            if(last < minv) last = maxv;
            else
            {
                res ++ ;
                last = minv;
                st = -1;
            }
        }
        i = j;
    }
    cout << res << endl;
    return 0;
}