Codeforces Round #420 (Div. 2) C. Okabe and Boxes 栈+last标记+贪心

My Solution

题意：有1~n这n个数，给出一个stack的push和pop的序列，要求在执行的过程中用尽可能少的重排次数，使得能够使pop的顺序是1~n的顺序。

栈+last标记+贪心

1~2*n个操作，用一个last标记最近一次重排的位置，初始为last = 0。

然后用一个栈表示上一次重排后push如的元素的栈结构。

每次remove，如果当前需要pop的cnt == top则直接从stack pop掉，

否则，如果栈空，且mp[cnt]出现的位置在last之前，则可以直接pop，

不然则需要一次重排，然后pop，并且清空当前栈。

复杂度 O(n)

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 3e5 + 8;

int mp[MAXN];
string s;
stack sta;

int main()
{
    #ifdef LOCAL
    freopen("c.txt", "r", stdin);
    //freopen("c.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int n, i, j, val, top = -1, last = 0, ans = 0, cnt = 1;
    cin >> n;
    for(i = 1; i <= 2*n; i++){ cin >> s;
        if(s[0] == 'a'){
            cin >> val;
            mp[val] = i;
            top = val;
            sta.push(val);
        }
        else{
            if(cnt != top){
                if(mp[cnt] <= last && sta.empty()){
                    ;
                }
                else{
                    last = i;
                    ans++;
                }
                while(!sta.empty()) sta.pop();
                top = -1;
            }
            else{
                sta.pop();
                if(!sta.empty())top = sta.top();
                else top = -1;
            }
            cnt++;
        }
    }
    cout << ans << endl;


    #ifdef LOCAL
    while(!sta.empty()) sta.pop();
    memset(mp, 0, sizeof mp);
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx