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

PineappleSummer · 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;
}