题解 BZOJ2457【双端队列】
小黑AWM
2019-02-23 21:45:48
### [题面描述以及洛谷提交链接](https://www.luogu.org/problemnew/show/T70263)
***
首先观察后，发现对于每个双端队列可以维护一个不减的序列。但是如果在维护的时候，按照输入的顺序对于每个数直接选择插入队首或者队尾，一旦之后出现了一个位于该队列的范围之中的数字便会导致队列不能连接在一起，或许可以尝试先一个数字一个队然后再合并但是显然时间成本过大。
那么既然读入时对于每个子问题进行处理会由于全局情况的不可确定性导致难以求解，我们不妨从整体的角度来考虑这个问题。
最终的目的是要将序列变成一个不减的序列，不妨先排序得到这个序列，然后再把序列分成若干个队列，显然地，我们要让分割出的队列尽量的长。
嗯但是因为我们操作的时候必须是**依次处理N个数**所以我们就要记录排好序的序列中每个元素在原来序列中的位置（以下称之为标号）。如样例数据$3, 6,0,9,6,3$ 排序之后是$0,3,3,6,6,9$而其中每个元素对应的原来的位置是$3,1,6,2,5,4$当然也可以是$3,6,1,5,2,4$或者其他的什么因为相同的元素的标号是可以随意互换而没有影响的。
发现因为原问题中的是双端队列所以我们需要保证分割出的队列中对应的标号满足先递减后递增，那么才可以被装入一个双端队列，就是必须按照原来的顺序从中间往两边放，由于相同的一堆数对应的标号可以互换，所以我们只需要求出当这样的谷最少的情况。就像这样只有两个谷。这时候可以贪心地将一连串相同的数的标号处理成单调的。
```
0 3 3 6 6 9
6
5
4
3
2
1
```
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;
const int maxn = 2e5 + 10;
int n,Min[maxn], Max[maxn], nxt[maxn], Log2[maxn], ans; // nxt[i]表示i位置之后和elemet[i]数值相同的的最后一个元素的位置+1
bool stat; // stat = 0递减, stat = 1 递增
pii elemet[maxn];
bool cmp(pii a, pii b){
return a.first < b.first;
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++)
cin >> elemet[i].first,
elemet[i].second = i;
sort(elemet+1, elemet+1+n, cmp);
for(int i = n; i >= 1; i--){
if(nxt[i] == 0){
nxt[i] = i+1;
Min[i] = elemet[i].second;
Max[i] = elemet[i].second;
}
if(elemet[i-1].first == elemet[i].first){
nxt[i-1] = nxt[i];
Min[i-1] = min(elemet[i-1].second, Min[i]);
Max[i-1] = max(elemet[i-1].second, Max[i]);
}
}
int key = Min[1];//初始状态递减
ans = 1;//每将一个递增转变为递减则答案加一
for(int i = nxt[1]; i <= n; i = nxt[i]){
int a = Max[i];
int b = Min[i];
if(!stat){//如果当前状态是递减的
if(a < key)//可以维持递减状态
key = b;//不去管它，更新谷底
else{
key = a;//更改状态为递增，更新山顶
stat ^= 1;
}
}else{//当前状态是递增的
if(b > key)//可以维持递增状态
key = a;
else{
key = b;//更改状态为递减，更新谷底，答案加一
stat ^= 1;
ans++;
}
}
}
cout << ans << endl;
return 0;
}
```