好贷网好贷款

fzu 1894 志愿者选拔(单调队列)

发布时间:2016-12-5 4:36:52 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"fzu 1894 志愿者选拔(单调队列)",主要涉及到fzu 1894 志愿者选拔(单调队列)方面的内容,对于fzu 1894 志愿者选拔(单调队列)感兴趣的同学可以参考一下。

单调队列的入门题型。学习斜率优化DP的一个铺垫。 需要注意的一点是:虽然单次操作的复杂度可能不是O(1),但是单调队列中的每个元素都只入队和出队了一次,这样平摊下来,单次操作的复杂度仍然是O(1)。 #include<stdio.h> #include<string.h> #define N 1000005 int a[N],mark[N]; int main() { int T; scanf("%d",&T); getchar(); while(T--) { char s[15]; scanf("%s",s); getchar(); int cnt,head,tail; head=tail=0; cnt=0; int i; i=1; while(scanf("%s",s),strcmp(s,"END")!=0) { if(s[0]=='C') { scanf("%s%d",s,&a[i]); while(head<tail&&a[i]>a[mark[tail-1]]) tail--; mark[tail++]=i; i++; } else if(s[0]=='G') { cnt++; if(cnt==mark[head]&&head!=tail) head++; } else if(s[0]=='Q') { if(head==tail) { printf("-1\n"); } else printf("%d\n",a[mark[head]]); } getchar(); } } return 0; }

上一篇:Java图形化界面GUI-01-----黑马程序员
下一篇:hdu 4638 树状数组

相关文章

相关评论