题解：AT_abc458_g [ABC458G] Children Yearn for the Evil Kindergarten

thy21171 · 2026-05-22 15:02:14 · 题解

这个贪心咋这么牛啊。

首先发现正着不好确定决策，于是正难则反。

题目是先加奖章，再考虑删人。所以我们是先考虑每个人的出逃代价，再考虑奖章用在哪些人身上。

维护一个优先队列，每个元素记录有 cnt 个人，每个人出逃的代价是 cost。我们肯定希望先把那些代价小的人处理掉。于是可以贪心的把钱花掉。

当剩下的钱不足以处理一个人时，可以找一个代价最小的人把这些钱在他身上花完，然后就做完了。

#include <bits/stdc++.h>
typedef long long ll;
const int N = 3e5 + 5;

int n;
ll a[N], b[N], c[N], sum;
struct Node { ll cost, cnt; Node(ll a, ll b) { cost = a; cnt = b; }  bool operator<(const Node &b) const { return cost > b.cost; } };
std::priority_queue<Node> que;

void run()
{
    scanf("%d", &n); sum = 0;
    while (!que.empty()) que.pop();
    for (int i = 1; i <= n; ++i)
        scanf("%lld%lld%lld", a + i, b + i, c + i);
    for (int i = n; i; --i) {
        sum += b[i]; que.push(Node(b[i] + c[i] - sum, (ll)1e9));
        ll cost = a[i], cnt = 0;
        while (cost > 0) {
            auto [a, b] = que.top(); que.pop();
            a += sum;
            if (cost >= a * b) cost -= a * b, cnt += b;
            else {
                ll rest = cost / a; cost -= rest * a; cnt += rest;
                if (!cost) que.push(Node(a - sum, b - rest));
                else que.push(Node(a - cost - sum, 1)), que.push(Node(a - sum, b - rest - 1)), cost = 0;
            }
        } que.push(Node(-sum, cnt));
    } printf("%lld\n", que.top().cnt);
}

int main()
{
    int T; scanf("%d", &T);
    while (T--) run();
    return 0;
}