首页 > 代码库 > 繁华模拟赛 Vicent与游戏
繁华模拟赛 Vicent与游戏
#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>#include<cmath>#include<vector>#include<queue>#include<map>#include<set>#include<stack>#include<cstdlib>#include<string>#include<bitset>#include<iomanip>#include<deque>#include<utility>#define INF 1000000000#define fi first#define se second#define N 2000005#define P 1000000007#define debug(x) cerr<<#x<<"="<<x<<endl#define MP(x,y) make_pair(x,y)using namespace std;typedef long long LL;typedef pair<int,int> pii;char _ch;inline void getint(int &_x){ _x=0; for(_ch=getchar();_ch>‘9‘||_ch<‘0‘;_ch=getchar()); for(;_ch<=‘9‘&&_ch>=‘0‘;_ch=getchar()) _x=_x*10+_ch-48;}int stk1[N],top1,stk2[N],top2,ans,n;//stk1是当前的单调栈,stk2存将要放到stk1中的元素//stk1里是单调不升的,stk2也是单调不升的int a;void Clear()//时间复杂度还能保持O(n){ int i,now,val; while(top1) { val=stk1[top1]; for(i=top1;i;i--) if(stk1[top1]!=stk1[i-1]) break; now=top1-i+1; top1=i-1; while(now/2)//两两合并成一个更大的 { stk1[++top1]=val+1; now-=2; } //for(int j=1;j<=top1;j++) //debug(stk1[j]); //cout<<endl; //ans=max(ans,stk1[1]); } ans=max(ans,stk1[1]);}int main(){ int i,j,now,val; freopen("vincent.in","r",stdin); freopen("vincent.out","w",stdout); cin>>n; for(i=1;i<=n;i++) { getint(a); stk2[++top2]=a; while(top2)//总共分5种情况 { if(!top1)//假如第一个栈为空 { //if(top2>1) //top2--; //else stk1[++top1]=stk2[top2--]; } else { if(stk1[top1]>stk2[top2])//假如第一个栈顶大于第二个栈顶 //if(top2>1)//假如第二个栈 //while(--top1);//清空 //else stk1[++top1]=stk2[top2--]; else if(stk1[top1]==stk2[top2])//假如第一个栈顶等于第二个栈顶 /* if(top2>1)//将两个元素合并成一个大的 { top2--; stk1[top1]++; } else*/ { stk1[++top1]=stk2[top2--];//相等就先放进去 } else if(stk1[top1]<stk2[top2]) { if(top1>1&&stk1[top1]==stk1[top1-1])//贪心合并栈1顶的两个元素,并放入栈2 { stk2[++top2]=stk1[top1]+1; top1-=2; } else { top1--; for(j=2;j<=top2;j++)//清空之前将部分栈2内的元素放到栈1内 stk1[++top1]=stk2[j]; Clear();//只能清空掉了 } } } //for(int j=1;j<=top1;j++) //debug(stk1[j]); //for(int j=1;j<=top2;j++) //debug(stk2[j]); //cout<<endl; } //for(int j=1;j<=top1;j++) //debug(stk1[j]); ans=max(ans,stk1[top1]); } //for(i=1;i<=top1;i++) //debug(stk1[i]); //cout<<endl; //debug(top1); Clear(); cout<<ans<<endl; return 0;}// davidlee1999WTK 2016/// srO myk Orz// ios::sync_with_stdio(false);//#pragma comment(linker, "/STACK:102400000,102400000") compiler c++,not g++/*164 4 4 3 3 3 1 1 2*/
繁华模拟赛 Vicent与游戏
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。