bzoj1510: [POI2006]Kra-The Disks(单调栈)

这道题可以O(n)解决，用二分还更慢一点

维护一个单调栈，模拟掉盘子的过程就行了

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn = 300010;
 6 int n,m,h[maxn],st[maxn],top,x,now;
 7 int main(){
 8     scanf("%d%d", &n, &m);
 9     top=0; h[0]=2000000000;
10     for (int i=1; i<=n; i++){
11         scanf("%d", &h[i]);
12         h[i]=min(h[i],h[i-1]);
13         st[++top]=i;
14     }
15     now=n+1;
16     for (int i=1; i<=m; i++){
17         scanf("%d", &x);
18         while (top && (st[top]>=now || h[st[top]]<x)) top--;
19         now=st[top];
20     }
21     printf("%d
", now);
22     return 0;
23 }