E. MEX and Increments

https://codeforces.com/problemset/problem/1619/E

用栈处理

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define rep(i,a,b) for(ll i=(a);i<=(b);i++)
#define dec(i,a,b) for(ll i=(a);i>=(b);i--)
#define pll pair<ll,ll>
using namespace std;
ll INF = 0x7f7f7f7f7f7f7f7f;
const int N = 2e5 + 5;
ll mod = 998244353;

ll n, a[N];

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll T;
    cin >> T;
    while (T--) {
        cin >> n;
        vector<ll> ans(n + 1, -1), tmp, cnt(n + 1);
        rep(i, 0, n - 1)
            cin >> a[i], cnt[a[i]]++;
        ll sum = 0;
        rep(i, 0, n) {
            if (i > 0 && cnt[i - 1] == 0) {
                if (tmp.empty())
                    break;
                sum += i - tmp.back() - 1;
                tmp.pop_back();
            }
            ans[i] = sum + cnt[i];
            while (i > 0 && cnt[i - 1] > 1) {
                cnt[i - 1]--;
                tmp.push_back(i - 1);
            }
        }
        rep(i, 0, n)
            cout << ans[i] << ' ';
        cout << 'n';
    }
    return 0;
}

View Code

原文链接: https://www.cnblogs.com/dealer/p/15805868.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍