题解：P11328 [NOISG 2022 Finals] Gym Badges

· · 题解

前言

这题细节挺多的。

读题

很容易发现，这题里每一个比赛的价值一定，那么就不难联想到反悔贪心。

思考

我们回忆一下返回贪心的常见做法（反悔堆）：

  1. 先把元素按一定顺序排序
  2. 逐次扫描元素，检查能否放进堆：如果能，直接放入并计数；如果不能，检查是否比堆顶更优再决策。

那么这题应该按什么顺序排序呢？

很容易想到，使用 l 来做关键字。

但是，这是错误的 （因为样例都过不去）。

这题与 P4053 非常像，但有一点很重要的区别：

是先“参加第 i 个比赛”然后“让自己的等级提升 X_i 并获得一个徽章”。

这意味着，如果我们在抉择着一场比赛时， level < l_i 且 level + x_i > l_i，这场比赛仍然可以参与。

那么，我们不应该用比赛参与前的 l_i 排序，而是应该使用比赛参与后的 l_i +x_i 来排序。

实现

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>

#define N 500005

using namespace std;

struct node_ { //比赛
    int l, x;
}node[N];

int n, level, ans; //比赛数量，当前等级，答案
priority_queue <int> q; //STL的优先队列是大根堆

bool cmp(node_ a, node_ b) {
    return a.l + a.x < b.l + b.x; //排序的比较
}

int main() {
    //输入
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &node[i].x);
    for (int i = 1; i <= n; i++)
        scanf("%d", &node[i].l);

    //排序
    sort(node + 1, node + 1 + n, cmp);

    //扫描
    for (int i = 1; i <= n; i++) {
        if (level <= node[i].l) {
            level += node[i].x;
            q.push(node[i].x);
            ans++;
        }
        else if (!q.empty() && q.top() > node[i].x && level - q.top() <= node[i].l){
            level -= q.top();
            level += node[i].x;
            q.pop();
            q.push(node[i].x);
        }
    }

    //输出
    printf("%d", ans);
    return 0;
}

复杂度分析

瓶颈在于排序，基本为 O (n log n)，可以通过本题。

结语

引用学长 White_Wat 的一句话：

一般来说，返回贪心有两种：一种是价值一定费用不一定；另一种是费用一定价值一定。在看到这两种情形的时候，可以立马尝试使用反悔堆解决问题。

不过做题的时候切记：把题读完整再开始思考，不要看到关键词就下判断然后开始敲代码。

~~不然就会这样：直接把 P4053 复制过来然后对着样例傻了一小时~~