前言

这题细节挺多的。

读题

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

思考

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

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

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

很容易想到，使用

l

来做关键字。

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

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

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

这意味着，如果我们在抉择着一场比赛时，

level < l_i

且

level + x_i > l_i

，这场比赛仍然可以参与。

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

实现

CPP

#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 复制过来然后对着样例傻了一小时~~

题解：P11328 [NOISG 2022 Finals] Gym Badges

文章操作

前言

读题

思考

实现

复杂度分析

结语

相关推荐

评论

题解：P11328 [NOISG 2022 Finals] Gym Badges