繁华模拟赛 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=;

    for(_ch=getchar();_ch>''||_ch<'';_ch=getchar());

    for(;_ch<=''&&_ch>='';_ch=getchar())

        _x=_x*+_ch-;

}

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-])

                break;

        now=top1-i+;

        top1=i-;

        while(now/)//两两合并成一个更大的

        {

            stk1[++top1]=val+;

            now-=;

        }

        //for(int j=1;j<=top1;j++)

            //debug(stk1[j]);

        //cout<<endl;

        //ans=max(ans,stk1[1]);

    }

    ans=max(ans,stk1[]);

}

int main()

{

    int i,j,now,val;

    freopen("vincent.in","r",stdin);

    freopen("vincent.out","w",stdout);

    cin>>n;

    for(i=;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>&&stk1[top1]==stk1[top1-])//贪心合并栈1顶的两个元素，并放入栈2

                    {

                        stk2[++top2]=stk1[top1]+;

                        top1-=;

                    }

                    else

                    {

                        top1--;

                        for(j=;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 ;

}

// 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

*/
秒客网

繁华模拟赛 Vicent与游戏

相关文章
