自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 23:07:37，当前版本为作者最后更新于2024-12-26 21:30:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

神奇模拟。

把城堡需要的兵力排个序，当 t1e 的兵力能买消耗最小的城堡时，判断一下不买该城堡的答案，与全局答案取 $\min$，然后直接默认买掉（如果不买更优那么后面就不会再更新全局答案），循环模拟一下就行。

大概就是这样：

il void mian(){
	read(n, x, y), readArr(a + 1, n);
	if (x + n <= y) return cout << "-1", void();
	if (x > y) return cout << "1", void();
	sort(a + 1, a + n + 1);
	int b1 = 0, b2 = 0, ans = 0, ret = inf / 2;//b1 是 t1e 的兵力，b2 是对手的兵力
	L(i, 1, n){
		int tim = (a[i] - b1 - 1) / x + 1, t = inf / 3;
		if (b1 >= a[i]) tim = 0;
		if (x > y) t = (b2 + 1 - b1 - 1) / (x - y) + 1;
		ckmin(ret, ans + t), ans += tim + 1, b1 += tim * x, b2 += tim * y;
		b1 -= a[i], b1 += x, x++, b2 += y;
	}
	write(min(ret, ans + (b2 + 1 - b1 - 1) / (x - y) + 1));
}