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到1e5t_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用公式算出新费用不断取最小值。这里自然就包括了k0的情况不用担心漏掉方案。如果所有士兵的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后i1到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后面所有需要补训的士兵是i1到n补训总费用为Σ(c_j * t_j) - k * Σ(c_j) suf1[i1] - k * suf2[i1]这个式子是从公式直接展开得到的所以两个后缀数组缺一不可。后缀和数组的初始化也很简单从n到1倒着循环suf1[n1] suf2[n1] 0; for (int i n; i 1; i--) { suf1[i] suf1[i1] a[i].t * a[i].c; suf2[i] suf2[i1] 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[n1] suf2[n1] 0; for (int i n; i 1; i--) { suf1[i] suf1[i1] a[i].t * a[i].c; suf2[i] suf2[i1] 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[i1] - k * suf2[i1]); 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。全部单练费用是13227。k1时费用是15后面的士兵补训2(2-1)7。k2时费用是2*5010。所以答案是7。用例二把C改小2 1 2 3 3 2全部单练还是7。k1时费用是1123。k2时费用是2102。答案变成2也就是连续两天集体训练第一天免费后面两天各花1元。这两个用例分别对应了“单练划算”和“集体训练划算”两种极端情况代码都能给出正确答案。4. 常见问题与避坑指南4.1 忘记减1导致答案偏大这是我见过最多人犯的错误。题目里“第一天免费集体训练”这个条件看起来只是一个小细节但直接影响所有t_i的取值。如果不减1公式里所有士兵都会多算一天训练费用答案自然偏大。有些同学可能会问能不能在最后答案里统一减去某个值不建议这么干因为第一天免费训练对每个士兵的效果都一样但如果在计算过程中不减1排序后的分界点、前缀和数值全都是错的最后根本不是简单减去一个常数能挽回的。4.2 乘法溢出为什么必须用long long这道题的数据范围里t_i可以到1e9c_i也可以到1e6级别两者相乘就是1e15远远超过int能表示的范围。如果不使用long long测评时一旦数据大一些结果就会变成负数或者乱码。这里不只是答案要用long long中间计算过程的每一项都要小心。比如k乘以Ck是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赛制一次提交错误可能就要多等很久提前自测真的值得。
蓝桥杯训练士兵题解：C语言实现贪心排序与前缀和优化
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到1e5t_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用公式算出新费用不断取最小值。这里自然就包括了k0的情况不用担心漏掉方案。如果所有士兵的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后i1到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后面所有需要补训的士兵是i1到n补训总费用为Σ(c_j * t_j) - k * Σ(c_j) suf1[i1] - k * suf2[i1]这个式子是从公式直接展开得到的所以两个后缀数组缺一不可。后缀和数组的初始化也很简单从n到1倒着循环suf1[n1] suf2[n1] 0; for (int i n; i 1; i--) { suf1[i] suf1[i1] a[i].t * a[i].c; suf2[i] suf2[i1] 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[n1] suf2[n1] 0; for (int i n; i 1; i--) { suf1[i] suf1[i1] a[i].t * a[i].c; suf2[i] suf2[i1] 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[i1] - k * suf2[i1]); 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。全部单练费用是13227。k1时费用是15后面的士兵补训2(2-1)7。k2时费用是2*5010。所以答案是7。用例二把C改小2 1 2 3 3 2全部单练还是7。k1时费用是1123。k2时费用是2102。答案变成2也就是连续两天集体训练第一天免费后面两天各花1元。这两个用例分别对应了“单练划算”和“集体训练划算”两种极端情况代码都能给出正确答案。4. 常见问题与避坑指南4.1 忘记减1导致答案偏大这是我见过最多人犯的错误。题目里“第一天免费集体训练”这个条件看起来只是一个小细节但直接影响所有t_i的取值。如果不减1公式里所有士兵都会多算一天训练费用答案自然偏大。有些同学可能会问能不能在最后答案里统一减去某个值不建议这么干因为第一天免费训练对每个士兵的效果都一样但如果在计算过程中不减1排序后的分界点、前缀和数值全都是错的最后根本不是简单减去一个常数能挽回的。4.2 乘法溢出为什么必须用long long这道题的数据范围里t_i可以到1e9c_i也可以到1e6级别两者相乘就是1e15远远超过int能表示的范围。如果不使用long long测评时一旦数据大一些结果就会变成负数或者乱码。这里不只是答案要用long long中间计算过程的每一项都要小心。比如k乘以Ck是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赛制一次提交错误可能就要多等很久提前自测真的值得。
