我们之前学习了如何使用STL中的队列 现在我们来看一道与队列有关的神奇的题（看似队列而非为队列）————双端队列
分析： 如果现在有一段序列 Ai，Ai+1，Ai+2，······，Aj-1，Aj 满足该双端队列的要求，即满足： Aj-1<…Ai+1<Ai<Ai+2…<Aj 即如一个二次函数一般的图 所以这道题的本质就在于，找有多少个谷底！！ 可以直接处理原始数据，也可以排序后处理下标，我处理的下标
代码如下
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <cmath> #include <iostream> #define MAXN 200100 using namespace std; struct node{ int v,ps; }a[200100]; int n; int mx[200100],mi[200100],cnt=0; int ans=0,flag=1,now=0x7f7f7f7f; bool cmp(node A,node B) { return A.v<B.v; if(A.v==B.v) return A.ps<B.ps; } int main() { freopen("deque.in","r",stdin); freopen("deque.out","w",stdout); cin>>n; for(int i=1;i<=n;i++) { cin>>a[i].v; a[i].ps=i; } sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++) { if(i==1||a[i].v!=a[i-1].v) { mx[cnt]=a[i-1].ps; mi[++cnt]=a[i].ps; } } mx[cnt]=a[n].ps; for(int i=1;i<=cnt;i++) { if(flag==0) { if(now>mx[i]) now=mi[i]; else { now=mx[i]; flag=1; } } else { if(now<mi[i]) now=mx[i]; else { flag=0; now=mi[i]; ans++; } } } cout<<ans; return 0; }