2024年蓝桥杯省赛A组有一道让人印象很深的题，叫“训练士兵”。如果你是用C语言参赛，这道题基本把排序、贪心、前缀和优化这几个省赛高频考点一锅端了，代码量不大，但思路一旦卡住，很容易绕进“模拟每一天”的坑里出不来。网上关于这道题的题解不少，但大部分是C++写的，直接改成C语言时，有人卡在结构体排序，有人卡在后缀和推导，还有人第一天的免费训练没处理好，样例能过、大数据直接挂。
这篇文章我就用C语言完整走一遍这道题，从题目拆解、核心思路、推导过程，到可提交的代码和测试用例，再到我踩过的几个坑，一次性讲清楚。适合刚刷完基础语法、准备冲省A的选手，也适合那些想搞懂“为什么这样贪心是对的”的人。
1. 题目到底在说什么：需求拆解与考点判断
1.1 还原题目场景与输入输出
这道题讲的是，你有n个士兵，第i个士兵需要训练t_i天，如果单独让这个士兵训练一天，要花c_i元。另外你还可以安排集体训练，花C元让所有士兵一起训练一天。重点来了：第一天是免费集体训练，不用花C。
输入格式就是第一行两个整数n和C，后面n行每行两个整数，表示每个士兵的t_i和c_i。要求输出最小总花费。
我第一次读题时，脑海里第一反应是“这不就是个带状态的模拟题吗”，每天要么集体训练，要么挑一个人单练，状态多到没法存。但一看数据范围就明白了，t_i可以非常大，根本不可能一天一天模拟，必须把问题数学化，找出最优解的数学结构，再通过排序和枚举来求解。
这里有一个很关键的直觉：集体训练是一个“普惠”操作，所有人都受益，而单独训练是“精准”操作，只有一个人受益。如果要花集体训练的钱，那一定是越早用越好，因为早用一天，就能让更多士兵少练一天。相反，如果决定某个士兵完全靠单练，那他在集体训练开始之前练还是之后练，效果是一样的。这个简单的直觉，最后会变成解题的钥匙。
1.2 一眼看出考什么：排序+贪心+前缀和
这道题从题型上说，是非常典型的“贪心 + 排序 + 前缀/后缀和优化”。省赛A组的题有个特点，它不会直接告诉你用什么算法，而是把一个看起来很自然的场景，包装成需要你抽象成数学模型的样子。
顺着这个思路，你会发现，一旦确定“集体训练到底进行多少天”，剩下的士兵需要补多少天单练，是可以直接算出来的。而“集体训练到底进行多少天”，这个值只可能是某个士兵的训练天数，因为多练半天或者多练一天但没让任何一个士兵“刚好完成”，都会造成浪费。
那怎么快速算出“超过k天的士兵，总共还要补多少训练费”？这就必须用排序把士兵按训练天数排好，再用后缀和维护费用信息。C语言里没有STL的sort，只能手写qsort，虽然麻烦一点，但逻辑反而更透明。
1.3 这道题在蓝桥杯省赛中的定位和得分策略
从分值上看，“训练士兵”属于那种“想通了就拿分，想不通就爆零”的中档题。它的难点不在代码实现，而在思路转化。如果你在考场上卡了半小时还没想清楚，我建议先跳过去做后面的题，因为这道题即使写一个暴力模拟，也只能过很少的数据点，性价比不高。
但如果思路通了，代码其实很短，大概50行左右，而且不太容易写错。我自己刷题时的习惯是，先看数据范围，再猜算法。n到1e5，t_i到1e9，一看就知道要O(n log n)级别的算法，排序是跑不掉的。然后想“排序之后干什么”，自然就会想到枚举分界点。这也是省赛题比较常见的出题套路：排序只是为了让你能快速计算某种函数值，真正的难点在找到那个“分界点”。
2. 核心思路：为什么排序后枚举“集体训练天数”是对的
2.1 两种操作的费效对比
先做一个很粗糙的分析：假设当前有m个士兵还没训练完，如果这一天选择集体训练，花费C，效果是所有人的剩余训练天数都减少1。如果这一天选择单独训练某个士兵，花费c_i，效果只是这个士兵的剩余天数减少1。
那么什么时候集体训练划算？最朴素的想法是，如果C比当前所有还没完成的士兵的单练费用之和还小，那就集体训练。但这忽略了一个问题：有的士兵再过一天就练完了，有的士兵还要练很多天，把“给快练完的人多练一天”和“给远没练完的人多练一天”看成同样价值，其实是把问题想简单了。
不过这个粗糙的对比里有一个有用的结论：集体训练相当于“一次买断当前所有人的一天”。如果某个士兵训练天数很短，他很容易被集体训练覆盖掉；如果训练天数很长，他就必须靠后面的单练来补。所以决定权并不在“每个人单练多少钱”，而在“哪些人能被集体训练的k天覆盖掉”。
2.2 从“每天决策”到“一次性枚举天数”的转化
既然不能逐天模拟，就要换个角度：假设最优方案中，集体训练的总天数是k，那么每个士兵i的完成情况完全由他需要的天数t_i决定：
- 如果t_i小于等于k，这个士兵在集体训练阶段就已经练完了，不需要单练。
- 如果t_i大于k，这个士兵在集体训练k天后，还剩下t_i - k天，这些天必须单独训练。
这样的话，总费用就是：
k * C + Σ (c_i * (t_i - k))，其中i满足 t_i > k这个公式把“每天怎么决策”彻底转化成了“只要确定k，费用就确定了”的数学表达式。而最优的k，一定等于某个士兵的t_i。为什么？因为如果k落在两个相邻的训练天数之间，比如t_3 < k < t_4，那么满足t_i > k的士兵集合是不变的，公式里后面的求和项不变，但前面的k*C会随着k增大而线性增大，所以你肯定不会选择一个区间内部的k，只会选择区间的端点，端点恰恰就是士兵的训练天数。
这个转化是整个题的灵魂。一旦理解了它，代码就只是套公式的问题了。
2.3 免费第一天到底怎么处理
题目里第一天免费集体训练，这个条件如果不处理，代码跑出来的答案会普遍偏大。最简单的处理方式，是在读入每个士兵的t_i后，立刻执行t_i = t_i - 1，意思是这个士兵在免费的第一天里已经训练了一天，剩下的天数才需要花钱。
这一步做完，整个问题就变成了一个“纯付费版”的训练问题：每天的集体训练要花C，单练要花c_i，不再有免费的干扰项。很多人样例不过，就是忘了这个减1的操作。
可能有人会问，如果把每个t_i都减1，那假设某个士兵t_i本身就是1，减完之后变成0，这不就乱了吗？其实没有乱，t_i等于0意味着这个士兵第一天就练完了，后面完全不需要为他花一分钱，这跟现实是吻合的。
2.4 边界情况：有人第一天就练完了
处理完减1之后，数组里会出现很多t_i为0的士兵。排序的时候，它们会排在前面。枚举k的时候，k取0就是“一天集体训练都不安排，剩下的人全部单练”，这天然对应了“完全不做集体训练”的方案。
所以最终的答案初始化时，可以直接用全部士兵单练的总费用，也就是Σ(c_i * t_i)。然后枚举每个士兵的t_i作为k，用公式算出新费用，不断取最小值。这里自然就包括了k=0的情况，不用担心漏掉方案。
如果所有士兵的t_i减1后都是0，那答案就是0，因为第一天免费训练就全部搞定了。这个边界情况很小，但很能检验你代码里初始化的值对不对。
3. C语言实现：从伪代码到可提交代码
3.1 数据结构与排序写法
用C语言实现，首先要定义一个结构体存士兵的两个字段：
typedef struct { long long t; // 剩余训练天数 long long c; // 单练一天的费用 } Soldier;这里必须都用long long，因为t_i的范围很大，t_i乘c_i可能直接爆int。
排序用qsort，需要手写比较函数。比较时不要写成return p->t - q->t，因为当两个long long的差值超过int范围时会出错。
int cmp(const void *x, const void *y) { Soldier *p = (Soldier *)x; Soldier *q = (Soldier *)y; if (p->t < q->t) return -1; if (p->t > q->t) return 1; return 0; }排序方向选择从小到大，这样枚举k的时候，前i个士兵的t_i都小于等于k，后i+1到n的士兵都大于k，分界非常干净。
3.2 后缀和数组的推导与计算
为了快速计算公式中的Σ(c_i * (t_i - k))，需要预处理两个后缀和数组：
- suf1[i]表示从第i个士兵到第n个士兵的c_i * t_i之和。
- suf2[i]表示从第i个士兵到第n个士兵的c_i之和。
那么对于第i个士兵作为分界点，k = t_i，后面所有需要补训的士兵是i+1到n，补训总费用为：
Σ(c_j * t_j) - k * Σ(c_j) = suf1[i+1] - k * suf2[i+1]这个式子是从公式直接展开得到的，所以两个后缀数组缺一不可。
后缀和数组的初始化也很简单，从n到1倒着循环：
suf1[n+1] = suf2[n+1] = 0; for (int i = n; i >= 1; i--) { suf1[i] = suf1[i+1] + a[i].t * a[i].c; suf2[i] = suf2[i+1] + a[i].c; }3.3 完整C代码
把前面的内容串起来，就能写出完整的可提交代码：
#include <stdio.h> #include <stdlib.h> typedef struct { long long t; long long c; } Soldier; Soldier a[100005]; long long suf1[100005], suf2[100005]; int cmp(const void *x, const void *y) { Soldier *p = (Soldier *)x; Soldier *q = (Soldier *)y; if (p->t < q->t) return -1; if (p->t > q->t) return 1; return 0; } int main() { int n; long long C; scanf("%d %lld", &n, &C); for (int i = 1; i <= n; i++) { scanf("%lld %lld", &a[i].t, &a[i].c); a[i].t--; // 第一天免费集体训练 } qsort(a + 1, n, sizeof(Soldier), cmp); suf1[n+1] = suf2[n+1] = 0; for (int i = n; i >= 1; i--) { suf1[i] = suf1[i+1] + a[i].t * a[i].c; suf2[i] = suf2[i+1] + a[i].c; } long long ans = suf1[1]; // 完全不集体训练 for (int i = 1; i <= n; i++) { long long k = a[i].t; long long cost = k * C + (suf1[i+1] - k * suf2[i+1]); if (cost < ans) ans = cost; } printf("%lld\n", ans); return 0; }这个代码的时间复杂度是O(n log n)，空间复杂度O(n)，在n为1e5的情况下非常稳。
3.4 给几个测试用例验证一下
我拿几个自己构造的数据跑了一下，验证这个代码是没有问题的。
用例一：
2 5 2 3 3 2减1后，两个士兵的t分别为1和2。全部单练费用是13+22=7。k=1时，费用是15+后面的士兵补训2(2-1)=7。k=2时，费用是2*5+0=10。所以答案是7。
用例二，把C改小：
2 1 2 3 3 2全部单练还是7。k=1时，费用是11+2=3。k=2时，费用是21+0=2。答案变成2，也就是连续两天集体训练，第一天免费，后面两天各花1元。
这两个用例分别对应了“单练划算”和“集体训练划算”两种极端情况，代码都能给出正确答案。
4. 常见问题与避坑指南
4.1 忘记减1导致答案偏大
这是我见过最多人犯的错误。题目里“第一天免费集体训练”这个条件，看起来只是一个小细节，但直接影响所有t_i的取值。如果不减1，公式里所有士兵都会多算一天训练费用，答案自然偏大。
有些同学可能会问，能不能在最后答案里统一减去某个值？不建议这么干，因为第一天免费训练对每个士兵的效果都一样，但如果在计算过程中不减1，排序后的分界点、前缀和数值全都是错的，最后根本不是简单减去一个常数能挽回的。
4.2 乘法溢出：为什么必须用long long
这道题的数据范围里，t_i可以到1e9，c_i也可以到1e6级别，两者相乘就是1e15，远远超过int能表示的范围。如果不使用long long，测评时一旦数据大一些，结果就会变成负数或者乱码。
这里不只是答案要用long long，中间计算过程的每一项都要小心。比如k乘以C，k是1e9量级，C是1e6量级，乘积是1e15，同样必须用long long。所以我干脆把所有可能参与乘法的变量全部声明成long long，省心。
4.3 排序相等元素怎么处理
按t排序时，如果两个士兵的训练天数相同，它们的先后顺序其实无所谓。但要注意，枚举分界点时，如果排序后连续多个士兵的t相等，那么枚举到它们时k都相同，计算出来的费用在数学上是完全一致的，重复计算不会影响最终答案，只会多跑几次循环，性能上完全可接受。
不过如果你像我一样有强迫症，也可以写一个去重逻辑，但完全没必要，反而容易引入bug。
4.4 运行超时排查
如果你写的是按天模拟的暴力代码，超时是必然的，因为t_i可以到1e9。这时不应该纠结优化常数，而应该重新审视整个思路，看能不能像上面一样把问题变成“枚举k + 前缀和查询”的模型。
如果你的代码已经是排序加枚举，但仍然超时，那要检查是不是在循环里又做了一次O(n)的求和。有些人看到公式时第一反应是每个k算一遍循环求和，这样总复杂度就是O(n^2)，照样过不了。正确做法一定是先用后缀和预处理，把每次求和的复杂度降到O(1)。
5. 从这题总结出的省A通用套路
5.1 贪心+排序题的思考路径
做多了蓝桥杯省A的题会发现，很多题表面上是模拟，本质是贪心。碰到这种题，我习惯按这个顺序想：先把题目里的操作简化成数学表达式，然后思考“最优方案长什么样”，最后考虑怎么快速枚举或贪心选择。
这道题里，最优方案就可以描述成“先集体训练k天，再单练剩下的人”。一旦确定了这个形态，问题就从“每天怎么选”变成了“k取多少”，性质完全不一样了。这种把时间维度上的连续决策压缩成一个参数的思想，在很多题里都能复用。
5.2 枚举分界点+前缀和/后缀和优化
“训练士兵”的另一个通用套路是“枚举分界点”。排序后，枚举一个位置，把数组切成两段，左段用某一种策略，右段用另一种策略，然后用前缀和或后缀和快速计算两段的代价。
这个套路在算法竞赛里非常常见，比如很多区间DP、背包变种、以及一些二维偏序问题里都能看到类似的思想。关键是你要能识别出“问题存在一个天然的分界点”。在这道题里，分界点就是“谁被集体训练覆盖，谁没被覆盖”，非常自然。
5.3 备赛建议：别只背模板，要练“转化”能力
如果你距离省赛还有一段时间，我建议多练这类“把场景抽象成数学模型”的题目。C语言的语法反而不用太担心，qsort、结构体、long long这些掌握好就够用了，真正决定你能不能做出来的，是能不能在考场上快速完成从题意到算法的转化。
平时刷题时可以刻意做几件事：看到题先猜复杂度，想清楚数据范围能接受什么算法；然后尝试把操作写成公式；实在没思路就去看题解的思路部分，但看完要自己把代码写一遍，不要抄。这样坚持一两个月，省A的题你会觉得没那么可怕。
我在实际写这道题时，也一度在“第一天减1”和“后缀和数组边界”之间反复折腾过。后来养成一个习惯：每道题写完代码后，先拿两个自己构造的小样例手算一遍，再提交，能省掉很多无意义的罚时。对于蓝桥杯这种OI赛制，一次提交错误可能就要多等很久，提前自测真的值得。
