首页 > 代码库 > 繁华模拟赛 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与游戏