首页 > 代码库 > CF 319B Psychos in a Line 【单调队列】
CF 319B Psychos in a Line 【单调队列】
给出一排神经病的编号1-n的某个排列
给出规则
一步能同时消除该数右边连续的小于该数的数
问几步能消到最后状态
在纸上试了试,觉得这个问题很有点像lis,但是苦于方法
突然看了一眼tags
单调队列
oh it is
可以把这些数字一个一个的加入单调队列中
同时记录每个数字被吃掉的场次
保持整个队列递减
策略如下
如果一个数进去没有弹出数,则这个数肯定是第一场就被消掉的
如果一个数进去弹出了一些数,则该数被吃掉的场次等于它弹走的所有数中最大的被吃掉的场次序号+1
因为,这个数肯定是在它弹掉的数之后被吃掉的(它被弹完后的队列中最后面一个数吃掉)
如果一个数进去弹出了所有的数,则这个数被吃掉的场次为0
当然,一开始是要找到从第一个开始的单调子串中的最后一个数作为这个队列的第一个数,并且场次为0
#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <iostream> using namespace std; const int NN=111111; int f[NN]; struct Q{ int x,pos; }q[NN*10]; int main(){ #ifndef ONLINE_JUDGE freopen("G:/in.txt","r",stdin); //freopen("G:/myout.txt","w",stdout); #endif int n,pos=0;cin>>n; for(int i=1;i<=n;i++) cin>>f[i]; for(int i=2;i<=n;i++){//找到一开始递增的数串中最后一个数 if(f[i]<f[i-1]){ pos=i; break; } } if(pos==0){//全递增 cout<<0<<endl; return 0; } int head=0,tail=0; int maxn=0; q[tail++]=(Q){f[1],1}; for(int i=pos;i<=n;i++){ if(f[i]<q[tail-1].x){//没有弹出数的是第一场就被吃掉的 q[tail++]=(Q){f[i],1}; maxn=max(q[tail-1].pos,maxn); }else if(f[i]>q[tail-1].x){//弹出数中最大场次+1是该数被吃掉的场次 int maxpos=0; while(f[i]>q[tail-1].x && tail>0){ maxpos=max(maxpos,q[tail-1].pos); tail--; } if(tail==0){ q[tail++]=(Q){f[i],1}; }else{ q[tail++]=(Q){f[i],maxpos+1}; } maxn=max(q[tail-1].pos,maxn); } } cout<<maxn<<endl; return 0; }
CF 319B Psychos in a Line 【单调队列】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。