【题目链接】:http://codeforces.com/contest/821/problem/C

【题意】



给你2*n个操作;

包括把1..n中的某一个数压入栈顶,以及把栈顶元素弹出;

保证压入和弹出操作都恰好各n个;

且压入的n个数字都各不相同;

在弹出栈的时候你可以把栈中的元素重新排列;

要求弹出的数形成的数列恰好组成1..n;

问你最少需要重新排列多少次;

【题解】



对于每一个remove操作,其实已经能确定接下来要输出的是几了;

在进行重新排操作的时候;

你可以假定自己“很聪明”,已经知道接下来要怎么排了,则栈顶以下的元素,

再次出现的时候,只要在重排操作之后没有新加元素,那么就可以直接认为在顶端!

如果有新元素,那只能跟栈顶元素比;

得到贪心策略.

↓

/*

    add x

        sta.push(x);

    remove;

        //y

    if (sta.empty()){

        continue;

    }else{

        if (sta.top()==y)

            continue;

        else{

            ope++;

            sta.clear();

        }

    }

    cout << ope <<　endl;

*/

【Number Of WA】



0



【反思】



想出来的时候,还是很激动的。



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 110;

stack <int> sta;

int n,x,y,ans;

char s[10];

int main(){

    //Open();

    Close();

    cin >> n;

    rep1(i,1,2*n){

        cin >> s;

        if (s[0]=='a'){

            cin >> x;

            sta.push(x);

        }else{

            y++;

            if (sta.empty()) continue;

            if (sta.top()==y){

                sta.pop();

            }else{

                ans++;

                while (!sta.empty()) sta.pop();

            }

        }

    }

    cout << ans << endl;

    return 0;

}