Buy Tickets hoj 单调队列优化DP的简单应用
/*题意是问能相互看见的人有多少对。只需要建一个单调递减的队列。枚举每一个i时，对前i-1个元素形成的单调队列里找>=a[i]的元素的个数即可。简单、*/#include <iostream>#include <stdio.h>#define maxn 500001using namespace std;int q[maxn];int a[maxn];int main(){ int n; while(scanf("%d",&n)==1) { int head=0,rear=0; int step=0; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1; i<n; i++) { while(head<rear&&q[rear-1]<a[i]) rear--; q[rear++]=a[i]; int t=rear; while(head<t) { t--; if(head==t) step++; else if(a[i+1]>=q[t]) step++; } } printf("%d\n",step); } return 0;}