警示后人:如果你的反悔贪心被 Hack 了
查看原帖
警示后人:如果你的反悔贪心被 Hack 了
735713
Azure_F楼主2025/7/21 19:16

如果你的反悔贪心类似于这样:

int n, k; ll m, tot = 0; int cnt = 0; pii s[N];
std::priority_queue<ll, std::vector<ll>, std::greater<ll> > q;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0), std::cout.tie(0);
	
	std::cin >> n >> k >> m;
	for(int i = 1; i <= n; ++i) std::cin >> s[i].p >> s[i].c;
	std::sort(s + 1, s + n + 1, [&](pii a, pii b) { return (a.c ^ b.c) ? a.c < b.c : a.p < b.p; });
	for(int i = 1; i <= n; ++i) {
		int d = s[i].p - s[i].c; ll ad = 0;
		if((int)q.size() < k) ad = s[i].c, q.push(d);
		else if(!q.empty() && q.top() < d) ad = q.top() + s[i].c, q.pop(), q.push(d);
		else ad = s[i].p;
		if(tot + ad > m) break; tot += ad, ++cnt;
	}
	std::cout << cnt;
	
	return 0;
}

那么是不对的,原因在于你不应该直接用排序的顺序去选牛。正确的方法见题解,要用三个堆动态地去选。

2025/7/21 19:16
加载中...