繁华模拟赛 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++
/*
16
4 4 4 3 3 3 1 1 2
*/