题解：P11328 [NOISG 2022 Finals] Gym Badges

swate114514 · 2025-12-20 15:53:28 · 题解

模拟赛的题，反悔了但是排序顺序猜错了。喜提 wa85……

首先我们可以用邻项交换法来确定排序顺序。

• 设交换前第 i 次可以参加比赛，第 i+1 次不可以参加比赛。
• 而交换后更优，第 i 和 i+1 次都可以参加比赛。

只要 \sum_{j=1}^{i-1}X_j\le L_i 即可参加比赛，那么可以设上面的和式为 A，前面的条件可以表示为：

我们知道，若 \text{(4)} 成立，\text{(1)} 一定会成立（因为 X_{i+1}>0），于是去掉 \text{(1)} 保留 \text{(4)} 即可。

同理，若 \text{(2)} 成立，\text{(3)} 一定会成立（因为 X_i \ge L_{i+1}-A，而 X_i>0，所以可得此时 A \le L_{i+1}），于是去掉 \text{(3)} 保留 \text{(2)} 即可。

于是条件成了：

把 A 放在左边，得

整理可得 L_{i+1}-X_i<A\le L_i-X_{i+1}。

于是 L_{i+1}-X_i< L_i-X_{i+1}，所以 L_{i+1}+X_{i+1}<L_i+X_i 时，情况有所改善。

所以按 L_i+X_i 升序排即可。

然后就比较套路了，当前这一个比赛无法满足时，显然替换掉前面比赛中 X_i 最大的一场，于是用大根堆来维护。 ::::success[AC code]

/*
Code by swate114514.
*/
#include <bits/stdc++.h>
#define int long long

using namespace std;

inline int read() {int s = 0, w = 1;char ch = getchar();while (ch > '9' || ch < '0') {if (ch == '-') w *= -1;ch = getchar();}while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + (ch ^ 48);ch = getchar();}return s * w;}
inline void write(int x) {if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');}

const int N = 1e5 + 5;
int n;
struct node {
    int h, p;
    bool operator < (const node& b) {
        return h + p < b.h + b.p;
    }
} a[N];
priority_queue<int> qu;

signed main() {
    freopen("invader.in", "r", stdin);
    freopen("invader.out", "w", stdout);
    n = read();
    for (int i = 1; i <= n; ++i) a[i] = {read(), read()};
    sort(a + 1, a + n + 1);
    int cnt = 0, tot = 0;
    for (int i = 1; i <= n; ++i) {
        if (tot > a[i].h) {
            if (!qu.empty() && qu.top() > a[i].p) {
                cnt--, tot -= qu.top();
                qu.pop();
            } 
        }
        if (tot <= a[i].h) {
            cnt++;
            tot += a[i].p;
            qu.push(a[i].p);
        } 
    }
    write(cnt);
    return 0;
} 

::::