当前位置：网站首页>AcWing 134. 双端队列

AcWing 134. 双端队列

2022-07-17 18:41:00 【hys__handsome】

（困难）队列+贪心

一、思路

这个问题很难直接求解,因为在不知道后面会有哪些数的情况下，我们作出的局部决策很可能造成某个数P与Q在同一队列中,这样只要后面出现了介于P和Q之间的数,不管放到哪里都会造成无解(无法把队列连成一个有序序列)。这种情况启发我们,必须考虑按照数值的大小顺序而不是读入的顺序进行计算。

因为sherry最后会把队列连成一个非降序列,所以我们不妨反过来思考，先把N个数A[1~N]从小到大排序,然后分成尽量少的几段,让每一段对应原问题中一个合法的双端队列。

二、做法

1、步骤

将所有元素升序排序。
接着计算具有单谷性质（元素 $i d$ 大小呈现U形分布）的段数，即为答案。为了方便计算单股性质的段数，需要将原来的升序序列切成每段元素值都相同的小段，然后根据当前是上升还是下降的状态区分地去一一去拼接。

2、拼接手法

需要手动去画图更容易理解。 $l a s t$ 是最后一个元素的 $i d$ ，如果当前是下降的，它就是下降这一段最小的 $i d$ ，如果当前是上升的那么他就是上升这一段最大的 $i d$ 。

设定初始状态是下降的。
如果当前状态是下降的：
1. 若 $l a s t$ 是大于这小段的最大 $i d$ ，那么拼接后仍是下降的，接着更新 $l a s t$ 成这小段的最小 $i d$ 。
2. 若 $l a s t$ 是小于这小段的最大 $i d$ ，那么拼接后为上升的并形成了一个单谷，接着更新 $l a s t$ 成这小段的最大 $i d$ 。
如果当前状态是上升的：
1. 若 $l a s t$ 是大于这小段的最小 $i d$ ，那么拼接后，前面那一段形成了一个单谷，然后从这小段开始新生成一个是下降转态的预备单谷，接着更新 $l a s t$ 成这小段的最小 $i d$ 。
2. 若 $l a s t$ 是小于这小段的最小 $i d$ ，那么拼接后仍是上升的，接着更新 $l a s t$ 成这小段的最大 $i d$ 。

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 200010;
pair<int,int> a[N];

int main(){
    
    cin.tie(0)->sync_with_stdio(false);
    int n; cin>>n;
    for(int i = 0; i < n; i++) {
    
        cin>>a[i].first;
        a[i].second = i;
    }
    sort(a,a+n);
    //dir=-1表示下降，反之上升
    //而last表示当前双端队列拼接后的最后一个元素下标
    int i = 0, last = n, dir = -1, res = 1;
    for(int i = 0; i < n; ){
    
        int j = i;
        while(j < n && a[i].first == a[j].first) j++;
        int minn = a[i].second, maxx = a[j-1].second;
        if(dir == -1) {
     //下降时
            if(last > maxx) last = minn;
            else {
     
                dir = 1;
                last = maxx;
            }
        } else {
     //上升时
            if(last < minn) last = maxx;
            else {
     
                dir = -1;
                last = minn;
                res++;
            }
        }
        i = j;
    }
    cout<<res;
    return 0;
}