自动搬运

查看原文

来自洛谷，原作者为

	PineappleSummer 时光飞逝啊

搬运于2025-08-24 22:57:29，当前版本为作者最后更新于2024-05-01 18:54:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P10387 [蓝桥杯 2024 省 A] 训练士兵

建议标签：贪心。

有一个显然的贪心思路：如果当前所有仍需要继续训练的士兵一次训练所需的金币总和小于 $S$，就使用组团训练；否则剩下的士兵全部单独训练。

输入时记 $cnt_i$ 为需要训练 $i$ 次的士兵一次训练所需的金币之和，$now$ 为所有士兵一次训练所需的金币之和，$Sum$ 为所有士兵单独训练所需的金币之和。

枚举组合训练的次数，记 $ans$ 为组合训练所需的金币之和。

对于第 $i$ 次组合训练：

• 如果 $now \ge S$，则说明还需要组合训练，$ans$ 加上 $S$，$Sum$ 减去 $now$，$now$ 减去 $cnt_i$。
• 如果 $now < S$，跳出循环，答案即为 $ans+Sum$。

记得开 long long。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
LL n, s, p[N], c[N], cnt[N], Sum, now, ans;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> s;
	for (int i = 1; i <= n; i++)
		cin >> p[i] >> c[i], cnt[c[i]] += p[i], now += p[i], Sum += p[i] * c[i];
	for (int i = 1; i <= 1e6; i++) {
		if (now < s)  break;
		ans += s;
		Sum -= now;
		now -= cnt[i];
	}
	cout << ans + Sum;
	return 0;
}