Nauuo and Cards

Created by LXC on Thu Aug 10 20:22:05 2023

https://codeforces.com/problemset/problem/1172/A

ranting: 1800

tag: greedy, implementation

problem

给出2n张牌，其中有n张牌是0，其余是1到n（各出现一次）。

现在你手上有n张牌，牌堆有n张牌。

每次操作可以从手上取出一张牌，放到牌底，然后抽走牌顶一张牌。

现在求最少操作次数，使得排堆的牌从顶至底为1到n升序。

solution

如果牌底k张牌已经是升序，我们尝试每次放置比牌底的值大1的牌。如果最后恰好能让牌堆升序，那么答案就是n-k。

否则采取另一种贪心思路

每次尝试放置cur到牌底，cur初始为1.

如果当前手上没有cur，那么最开始放置1到牌低的时间应该延后一次。

如果手上有cur则直接将cur放入牌底，并增加cur。

最后我们知道需要延后多少次才能让1号牌放置首先放入牌底，并保证放后续的牌都能升序。

延后的次数+n就是答案。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto& i : a)
        cin >> i;
    for (auto& i : b)
        cin >> i;
    auto check = [&]() {
        int p = 0;
        for (int i = 0; i < n; i++) {
            if (b[i] == 1)
                p = i;
        }
        int ok = 1;
        for (int i = p; i < n; i++) {
            if (b[i] != i - p + 1)
                ok = 0;
        }
        if (ok) {
            set<int> st(a.begin(), a.end());
            int cur = n - p + 1;
            for (int i = 0; i < p; i++) {
                if (st.count(cur))
                    cur++;
                else
                    return false;
                st.insert(b[i]);
            }
            cout << p << "\n";
            return true;
        }
        return false;
    };
    if (check())
        return;
    set<int> st(a.begin(), a.end());
    int add = 0, cur = 1;
    for (int i : b) {
        // cout << i << " ";
        if (st.count(cur))
            cur++;
        else
            add++;
        st.insert(i);
    }
    // cout << "\n";
    cout << n + add << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}