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

时间:2022-05-13 09:26:31

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

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

 #include<stdio.h>
 #include<string.h>
 #include<algorithm>
 using namespace std;
 ;
 int n,m,h[maxn],st[maxn],top,x,now;
 int main(){
     scanf("%d%d", &n, &m);
     top=; h[]=;
     ; i<=n; i++){
         scanf("%d", &h[i]);
         h[i]=min(h[i],h[i-]);
         st[++top]=i;
     }
     now=n+;
     ; i<=m; i++){
         scanf("%d", &x);
         while (top && (st[top]>=now || h[st[top]]<x)) top--;
         now=st[top];
     }
     printf("%d\n", now);
     ;
 }