题解：AT_abc388_d [ABC388D] Coming of Age Celebration

· · 题解

题目分析

考虑用优先队列。

观察题目发现，第 i 个外星人成年后，要给后面 n - i 个外星人每人一个石头，当然如果他自己没有石头就不用给。所以我们可以建一个小根堆，让石头少编号小的外星人排在前面，因为编号越小说明他要给的石头就越多。

一开始，我们先把第一个外星人入队，因为他不会收到石头要给后面每一个外星人石头，所以他最终的石头个数就是 \max(a_1 - (n - 1), 0)。接下来，如果队首的外星人石头没了，就把他出队。此时队里的外星人都要给今年要成年的外星人石头，所以当前外星人会获得队里外星人个数的石头，然后再把当前外星人入队，当前外星人最终的石头个数同理，就是 \max(a_i - (n - i), 0)。

代码

#include <bits/stdc++.h>
#define ft first
#define sd second
#define endl '\n'
#define pb push_back
#define md make_pair
#define gc() getchar()
#define pc(ch) putchar(ch)
#define umap unordered_map
#define pque priority_queue
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 bint;
typedef pair<int, int> pii;
typedef pair<pii, int> pi1;
typedef pair<pii, pii> pi2;
const ll INF = 0x3f3f3f3f;
inline ll read()
{
    ll res = 0, f = 1;
    char ch = gc();
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = gc();
    while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = gc();
    return res * f;
}
inline void write(ll x)
{
    if (x < 0) x = -x, pc('-');
    if (x > 9) write(x / 10);
    pc(x % 10 + '0');
}
inline void writech(ll x, char ch) { write(x), pc(ch); }
const int N = 5e5 + 5;
ll a[N];
struct node {
    int i;
    bool operator < (const node &cmp) const { return a[i] + i > a[cmp.i] + cmp.i; } // 重载运算符 
};
pque<node> q; // 小根堆 
int main()
{
    int n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    q.push(node{1});
    writech(max(a[1] - (n - 1), 0ll), ' ');
    for (int i = 2; i <= n; i++)
    {
        while (!q.empty() && a[q.top().i] - (i - q.top().i) < 0) q.pop(); // 没有石头的外星人出队 
        a[i] += q.size(); // 加上队里外星人个数 
        q.push(node{i}); // 入队 
        writech(max(a[i] - (n - i), 0ll), ' '); // 答案 
    }
    return 0;
}