自动搬运

查看原文

来自洛谷，原作者为

	Little_x_starTYJ 愿时光能缓，愿故人不散！ || 众所周知，如果把灯泡放在嘴里，即使你自己一个人也取得出来灯泡。

搬运于2025-08-24 22:53:34，当前版本为作者最后更新于2024-01-09 16:49:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解题思路

这道题目代码很短，但是思路很难想。

我们先按照奶牛重量排序，不难想到，最重奶牛一定要放在奶牛塔的最底层，只有这样我们才能保证奶牛数目最大，然后向上搭上第一头满足 $w_{top}-w_i\geq k$ 的奶牛，以此类推。

然后我们就会发现，这就是贪心，于是记录当前的 $m$ 表示这头牛可以搭在多少座塔上，那么我们就可以知道，实际符合要求的放下的奶牛的头数是 $\min(m,a_i)$ 头。

当我们将奶牛搭在塔上后，会有 $\min(m,a_i)$ 个塔的塔顶被修改，也就是说，这几个塔有可能还可以继续搭下一头奶牛，也有可能不可以搭下一头奶牛，所以我们还需要再次统计一下可以搭的塔的数量。

我们又要想想怎么快速统计可以搭的塔的数量。首先，当 $m\ge a_i$ 时有 $m-a_i$ 个塔可以搭奶牛。既然有 $\min(m,a_i)$ 个塔是搭过当前重量的奶牛的，那么我们把这些塔一起处理，如果 $w_{top}-w_{i + 1}\geq k$，那么这些塔都是可以继续搭奶牛的，如果塔顶连重量较小的奶牛都搭不上，那么我们没有必要再找下去了。

AC CODE:

#include <stdio.h>
#include <algorithm>
struct node {
	int a, b;
} c[200010];
bool cmp(node a, node b) {
	return a.b < b.b;
}
int ans[200010], id = 1;
long long res;
int main() {
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++)
		scanf("%d%d", &c[i].b, &c[i].a);
	std::sort(c + 1, c + 1 + n, cmp);
	for (int i = 1; i <= n; i++) {
		while (id < i && c[i].b - c[id].b >= k)
			m += ans[id++];
		ans[i] = m < c[i].a ? m : c[i].a; //系统自带的min有点慢
		m -= ans[i], res += ans[i];
	}
	printf("%lld", res);
	return 0;
}