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

题目传送门：P10387 训练士兵

一、题目描述

蓝桥王国有 n 名士兵，第 i 名士兵每次训练需要花费 pᵢ 枚金币，要成为顶尖战士需要至少训练 cᵢ 次。王国提供组团训练方案：一次性训练所有士兵各一次，花费固定 S 枚金币。求让所有士兵成为顶尖战士的最小花费。

二、题目分析

我们需要在两种训练方式中做出最优选择：

1. 单独训练：每次训练一个士兵，花费 pᵢ 金币
2. 组团训练：一次性训练所有士兵各一次，花费 S 金币

关键在于如何组合这两种方式以达到最小总花费。

三、解题思路

采用贪心算法：

1. 将士兵按所需训练次数 cᵢ 从小到大排序
2. 对于每个士兵，比较当前剩余士兵单独训练总成本和组团成本 S
3. 如果组团更划算，则尽可能多用组团训练；否则用单独训练

四、算法讲解

算法原理

贪心算法：每次选择当前最优的决策（组团或单独训练），从而希望达到全局最优。

使用场景

适用于问题可以分解为多个子问题，且每个子问题的最优解能导致全局最优解的情况。

实现步骤

1. 计算所有士兵单独训练的总成本 sum
2. 按 cᵢ 排序士兵
3. 遍历士兵：
   • 如果 sum ≥ S，使用组团训练
   • 否则，使用单独训练
4. 更新剩余训练需求和成本

示例解析

输入：

3 6
5 2
2 4
3 2

处理过程：

1. 排序后：(5,2), (3,2), (2,4)
2. 处理(5,2):
   • sum=10 ≥ 6 → 组团训练2次，花费12
   • sum=10-5=5, used=2
3. 处理(3,2):
   • 已满足训练次数
4. 处理(2,4):
   • 还需2次，sum=5 < 6 → 单独训练，花费4
     总花费：12 + 4 = 16

五、代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int n, s;
struct node
{
    int p, c;
} a[N];

bool cmp(node a, node b)
{
    return a.c < b.c; // 按训练次数排序
}

int ans;
void solve()
{
    cin >> n >> s;
    int sum = 0; // 所有士兵单独训练的总成本
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].p >> a[i].c;
        sum += a[i].p;
    }
    sort(a + 1, a + 1 + n, cmp); // 排序
    int used = 0; // 已通过组团训练覆盖的次数
    for (int i = 1; i <= n; i++)
    {
        if (sum >= s) // 组团更划算
        {
            ans += (a[i].c - used) * s;
            sum -= a[i].p; // 该士兵后续不再需要单独训练
            used = a[i].c; // 更新已覆盖次数
        }
        else // 单独训练更划算
        {
            ans += (a[i].c - used) * a[i].p;
            sum -= a[i].p;
        }
    }
    cout << ans;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

六、重点细节

1. 排序依据：必须按 cᵢ 排序，确保先处理需要较少训练的士兵
2. sum的更新：每次处理后要减去当前士兵的 pᵢ，因为后续训练不再需要单独训练他
3. used变量：记录已通过组团训练覆盖的次数，避免重复计算

七、复杂度分析

• 时间复杂度：O(n log n)，主要来自排序
• 空间复杂度：O(n)，存储士兵信息

八、总结

本题通过贪心算法，在每次决策时选择当前最优的训练方式（组团或单独），逐步解决问题。关键在于：

1. 正确的排序策略
2. 合理维护剩余训练需求和成本
3. 准确计算两种训练方式的性价比

这种贪心思路在类似的资源分配问题中非常有效，能高效地找到最优解。