[数据结构与算法]P2107 小Z的AK计划(反悔贪心)

小Z的AK计划 - 洛谷https://www.luogu.com.cn/problem/P2107这一题刚出来习惯性的想到直接走一趟反悔操作然后最后记录的值就是最大，但我发现中间因为需要考虑走路时间的因素会导致有些思考时间少的机房直接不走了去下一个机房了从而错过了最优解，下面贴一下我第一次写时候的错误代码

会被这样一组数据hack掉

5 18

1 8

2 8

4 7

6 3

7 1

struct node {
	ll x, t;
};
node s[MAXN];

bool cmp(node a, node b) {
	if (a.x == b.x)
		return a.t < b.t;
	return a.x < b.x;
}

int main() {
	int n;
	ll m;
	int ans = 0;
	ll time = 0;
	scanf("%d %lld", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%lld %lld", &s[i].x, &s[i].t);
	}
	priority_queue<ll> que;
	sort(s + 1, s + n + 1, cmp);
	for (int i = 1; i <= n; i++) {
		if (s[i].t + time + s[i].x <= m) {
			time += s[i].t;
			que.push(s[i].t);
			ans++;
		} else {
			if (!que.empty() && s[i].t < que.top()) {
				if (time + s[i].x + s[i].t - que.top() <= m) {
					time += s[i].t - que.top();
					que.pop();
					que.push(s[i].t);
				}
			}
		}
	}
	printf("%d", ans);
	return 0;
}

再来看看正确的代码，我们需要在路上一直更新AC数，并更新最大值，一旦碰到有机房不能AC的就考虑反悔之前的机房，最后直到无法AC就可以退出了，这样的话不会遗漏掉。

struct node {
	ll x, t;
};
node s[MAXN];

bool cmp(node a, node b) {
	if (a.x == b.x)
		return a.t < b.t;
	return a.x < b.x;
}

int main() {
	int n;
	ll m;
	scanf("%d %lld", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%lld %lld", &s[i].x, &s[i].t);
	}
	sort(s + 1, s + n + 1, cmp);
	int ans = 0;
	int rec = 0;
	ll time = 0;
	priority_queue<ll> que;
	for (int i = 1; i <= n; i++) {
		rec++;
		que.push(s[i].t);
		time += s[i].t;
		while (!que.empty() && time + s[i].x > m) {
			time -= que.top();
			rec--;
			que.pop();
		}
		if (time + s[i].x > m)
			break;
		ans = max(rec, ans);
	}
	printf("%d", ans);
	return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖