今天看到这个题很有意思就做了一下
题目是acwing 134 题 传送门
这是很特殊的一道题，能想到正解确实挺难，观察双端队列插入有个性质小数在前大数在后，所以排序后的数组下标如果是波谷的话就可以直接放到一个队列里面，具体情况模拟一下就知道了，这样我们就把这个问题转化为求最少波谷的问题，那么如何求最少波谷这个问题呢？就可以把相同的一段数字尽可能让它单调就行了，也就是存在两种情况，单调上升和单调下降，（通过画图可以看出）如果不能让它保持单调的话就转向就可以了。具体见代码：
#include <iostream> #include <algorithm> using namespace std; const int N =2e5+10; pair<int,int> a[N]; int main(){ int n; cin>>n; for(int i=0;i<n;i++){cin>>a[i].first;a[i].second=i;} sort(a,a+n); int last=0x3f3f3f3f; int dir=-1; int res=0; for(int i=0;i<n;){ int j=i; while(j<n&&a[j].first==a[i].first){ j++; } int minidx=a[i].second; int maxidx=a[j-1].second; if(dir==-1){ if(last>=maxidx){ last=minidx; } else { dir=1; last=maxidx; } } else { if(last<=minidx){ last=maxidx; } else{ dir=-1; res++; last=minidx; } } i=j; } res++; cout<<res<<endl; }
原文：https://www.cnblogs.com/kstranger/p/13329423.html