拿今年蓝桥杯省赛的《三国游戏》来说它表面上是一道模拟三国对抗的题目实际上考的是贪心加排序属于竞赛里非常典型的“转化后求最优”问题。很多同学第一次看到它第一反应是去枚举所有事件组合结果发现n一上来就是10的5次方量级直接傻眼。这道题的精髓在于先把“哪个国家赢”这件事拆开再把每个事件对胜利局面的贡献算成一个数最后用排序加前缀和解决。这篇文章我会从暴力思路讲起把贪心为什么可行、代码怎么写、容易踩哪些坑全部讲透无论你是准备蓝桥杯Java组、C组还是Python组这套思路都能直接照搬。1. 题目到底在问什么1.1 先读清楚题面题面大意是这样的有A、B、C三个国家初始兵力都是0。现在有n个事件每个事件会给三个国家分别增加一定的兵力。你可以从这n个事件中任意挑选若干个执行问最多能挑多少个事件使得执行完这些事件之后存在一个国家它的兵力严格大于另外两个国家兵力之和。如果无论如何都不存在这样的方案输出-1。这句话里有几个要点值得圈出来。第一是“任意挑选”意味着顺序无所谓你可以跳过一些事件这本质上是一个子集选择问题。第二是“严格大于”也就是胜利国的兵力要大于另外两国的兵力相加等于都不行这一点在写代码时非常容易忽略。第三是“最多能挑多少个事件”不是问你能不能让某个国家赢而是问在保证能赢的前提下事件数量要最大化。我用一组自己手造的数据来演示。假设n4四个事件分别给三国增加的兵力是4 1 1 2 5 2 1 2 6 3 3 1肉眼看一下如果全选A的总兵力是421310B是152311C是126110。B虽然最高但B11并没有大于AC20所以全选不是一个胜利方案。如果只选第1个和第4个事件A437B134C112此时A7大于BC6A国获胜事件数是2。我还可以继续试着加事件吗再加第2个事件A9B9C4A不大于13加第3个事件也不行。所以这组数据的最优解是2。接下来的所有推导我都会围绕这组数据展开。1.2 两个容易被忽略的题眼很多人在这个题上翻车根本原因不是贪心写不出来而是题面理解出了偏差。第一个偏差是把“存在一个国家获胜”理解成“三个国家轮流比较大小”然后试图模拟某种博弈过程。实际上题目根本没有博弈事件是你自己挑的三个国家都是被动接收兵力不存在谁先手谁后手的问题。它就是一个单人的选择优化题。第二个偏差是忽略“严格大于”。我见过有同学在判胜负条件时写成了x y z结果样例过了自己构造的数据也过了一到线上评测就错。原因就在于“等于”的情况会让一个国家在加完某个事件后恰好和另外两国的总和持平这种局面事件数量虽然多但并不是合法胜利局面。竞赛题里凡是用到“大于”“小于”这种比较词一定要先确认有没有“严格”二字这直接决定代码里是写大于号还是大于等于号。另一个容易忽略的点是“最多能挑多少个事件”。这句话意味着即使某个事件对胜利没有正向帮助只要它不影响胜利条件理论上就可以被选进来。比如某个国家的净收益本来就是0加上之后它的兵力优势不变那这种事件选进来也不会破坏胜利局面。这个细节在后面写贪心的时候会体现出来到时候我再细说。2. 从暴力到正解为什么是排序贪心2.1 暴力枚举为什么不可行先看最朴素的想法n个事件每个事件选或者不选一共2的n次方种方案然后对每种方案检查三个国家里有没有一个能赢。这个思路在n很小的时候完全没问题比如n小于等于15用状态压缩枚举子集代码好写也不会超时。但蓝桥杯省赛里这道题的数据范围通常是n最大能到10的5次方级别2的10万次方这个数字大得没有意义暴力枚举连边都摸不到。那动态规划行不行可以想到用dp[i][a][b][c]表示前i个事件之后三国兵力分别达到多少时最多选了多少事件但a、b、c的范围可能到10的14次方量级状态根本开不出来。这个题也塞不了什么复杂数据结构因为每个事件的贡献是三个值不是单纯的区间或单点。所以结论是必须在思路上做转化把它变成一个一维问题然后套一个O(n log n)级别的贪心算法这才是正解的方向。2.2 核心转化把多维比较压缩成一维差值假如我们最终想让A国获胜那胜利条件就是A的兵力严格大于B加C的兵力。设A选了某几个事件后总兵力分别记为sumA、sumB、sumC胜利条件就是sumA sumB sumC。这个式子可以改写成sumA - sumB - sumC 0。注意左边这个差值是一个标量只跟选中的事件集合有关而每个事件对差值的贡献就是a[i] - b[i] - c[i]。这样一来问题就被压缩成了一维我想让A获胜就只看每个事件对差值dA[i] a[i] - b[i] - c[i]的贡献数值越大越有利于A赢。然后从这些贡献值里挑尽可能多的数使得它们的和大于0。同理想让B获胜就考虑dB[i] b[i] - a[i] - c[i]想让C获胜就考虑dC[i] c[i] - a[i] - b[i]。三个国家各算一遍取事件数最多的那个作为答案。这里我用刚才那组数据验证一下。A获胜时四个事件的dA分别是第1个事件4 - 1 - 1 2 第2个事件2 - 5 - 2 -5 第3个事件1 - 2 - 6 -7 第4个事件3 - 3 - 1 -1从直观上看第1个事件对A获胜是纯加分第4个事件虽然扣分很少但扣了之后A的兵力优势可能还是正的所以它也可能被选上。第2个和第3个事件扣分太多大概率不能选。接下来要解决的就是给定一堆数最多选多少个才能让和大于0同时又要让数量尽量多。2.3 排序加转折判断的贪心逻辑现在问题变简单了有一堆数要选尽可能多的数选出来的和大于0。最优策略是什么直觉上是先选大的数再选小的数因为大的数能帮我们把和撑高然后才有余量去容纳那些带来负贡献但又不至于把和压到0以下的数。于是做法就是把这一堆贡献值从大到小排序然后从头开始累加只要当前累加和大于0就继续选下一个事件一旦累加和小于等于0就停止因为后面的事件贡献值只会更小或者相等加上去只会让累加和更低不可能再转正了。为什么排序后遇到非正就可以停止这个需要想清楚。假设排序后是w[0], w[1], ..., w[n-1]当前累加到某个位置时sum w[i] 0。由于w[i1] w[i]那么sum w[i1] sum w[i] 0后面的所有值加起来只会让sum更小。也就是说从第i个事件开始之后的所有事件都已经不可能让前缀和重新回到正数了。这个性质正是排序贪心成立的依据也是这题最关键的一步证明。再回到刚才的数据。A的四个dA排序后是2, -1, -5, -7。累加第一个2sum2大于0事件数记为1。累加第二个-1sum1仍然大于0事件数记为2。累加第三个-5sum-4小于等于0停止。所以A最多能选2个事件和我一开始手算的结果一致。注意这里第二个位置上的-1是第4个事件它本身是负数但因为sum还扛得住所以依然被选中这一个细节恰恰是很多人会写错的点。3. 三种语言的代码实现3.1 C版本最简洁的竞赛写法C写这道题非常顺手主要得益于STL里的vector和sort。核心逻辑封装成一个函数传入获胜方数组和另外两个数组返回“在该国获胜的前提下最多能选的事件数”。三个国家各调一次取最大值如果最大值是0说明一个事件都凑不出胜利局面输出-1。#include bits/stdc.h using namespace std; typedef long long ll; int calc(const vectorll x, const vectorll y, const vectorll z) { int n x.size(); vectorll w(n); for (int i 0; i n; i) { w[i] x[i] - y[i] - z[i]; } sort(w.begin(), w.end(), greaterll()); ll sum 0; int cnt 0; for (int i 0; i n; i) { sum w[i]; if (sum 0) cnt; else break; } return cnt; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorll a(n), b(n), c(n); for (int i 0; i n; i) { cin a[i] b[i] c[i]; } int ans 0; ans max(ans, calc(a, b, c)); ans max(ans, calc(b, a, c)); ans max(ans, calc(c, a, b)); cout (ans 0 ? -1 : ans) \n; return 0; }几个细节说一下。第一所有兵力相关的变量必须用long long类型因为n最大可以到10的5次方每个事件的兵力增量也可能到10的9次方三者相减后虽然单个值的绝对值相对可控但累加和完全可能超过int范围。第二sort的第三个参数用greater ()表示降序注意尖括号里的类型要和vector元素类型一致。第三calc函数里传入的三个数组都不需要修改所以用const引用既安全又避免拷贝。3.2 Java版本注意Long和long的坑Java写法和C几乎没有差别最大的坑在于排序。如果用一个long[]数组直接Arrays.sort后是升序想降序排序就要么自己写比较器要么先把long[]转成Long[]。比较器不能用在基本类型数组上这是Java初学者很容易踩的坑。import java.util.*; public class Main { static int calc(long[] x, long[] y, long[] z) { int n x.length; Long[] w new Long[n]; for (int i 0; i n; i) { w[i] x[i] - y[i] - z[i]; } Arrays.sort(w, Collections.reverseOrder()); long sum 0; int cnt 0; for (int i 0; i n; i) { sum w[i]; if (sum 0) cnt; else break; } return cnt; } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); long[] a new long[n], b new long[n], c new long[n]; for (int i 0; i n; i) { a[i] sc.nextLong(); b[i] sc.nextLong(); c[i] sc.nextLong(); } int ans Math.max(calc(a, b, c), Math.max(calc(b, a, c), calc(c, a, b))); System.out.println(ans 0 ? -1 : ans); } }这里我把w声明成Long[]这样Collections.reverseOrder()才能生效。如果你非要写性能更好的基本类型long[]那就需要自己写一个降序排序逻辑比如用Arrays.sort然后反转或者写自定义比较器但传参时改用List 。竞赛场景下我更推荐直接用Long[]代码量小、思路清楚性能损失在1e5的数据规模下完全可以忽略。计算返回值时Math.max里我嵌套了两层本质上就是三次calc取最大值。读入时我用的是Scanner如果追求极限速度可以换StreamTokenizer或者BufferedReader不过对于省赛B组这种题Scanner已经够用没必要提前优化到那个程度。3.3 Python版本代码最短但要注意输入方式Python的写法最贴近数学表达用列表推导式一行就能算出贡献值数组排序也只需要sort(reverseTrue)。要注意的是千万不能用input()一行一行读n等于1e5的时候会慢到让你怀疑人生必须用sys.stdin.read()一次性读入全部数据再解析。import sys def calc(x, y, z): w [x[i] - y[i] - z[i] for i in range(len(x))] w.sort(reverseTrue) total 0 cnt 0 for v in w: total v if total 0: cnt 1 else: break return cnt def main(): data sys.stdin.read().split() if not data: return idx 0 n int(data[idx]) idx 1 a [0] * n b [0] * n c [0] * n for i in range(n): a[i] int(data[idx]) b[i] int(data[idx 1]) c[i] int(data[idx 2]) idx 3 ans max(calc(a, b, c), calc(b, a, c), calc(c, a, b)) print(-1 if ans 0 else ans) if __name__ __main__: main()Python里int没有溢出问题所以这里不用像C和Java那样小心翼翼但反过来也要注意性能。calc函数内部虽然会复制出一个w列表但n最多1e5三次调用下来总拷贝量是可控的。整个算法的时间主要花在排序上Python的sort是Timsort实测在1e5的数据规模下表现很好。4. 复杂度分析与边界自测4.1 时间复杂度和空间复杂度这个解法的复杂度构成很简单生成贡献值数组需要O(n)排序需要O(n log n)前缀和累加需要O(n)。我们对三个国家各做一次所以总时间复杂度是O(3 * n log n)也就是O(n log n)。空间上每次calc函数里都会生成一个长度为n的数组w所以额外空间是O(n)。n 1e5的情况下O(n log n)的排序大概是十几万次比较操作加上常数整体运行时间在1秒以内蓝桥杯的时间限制通常是1到2秒完全没有压力。相比暴力的2的n次方这个复杂度已经是最优级别了因为排序本身的下界就是n log n在这个模型的限制下很难再往下降。4.2 边界情况逐个过边界测试是竞赛里保命的关键。第一个边界是n1。如果那一个事件本身就能让某个国家严格大于另外两国之和那答案就是1否则就是-1。用算法跑一遍比如只有一个事件(5,2,2)A的贡献值是5-2-21排序后累加为1大于0cnt1答案就是1。如果只有一个事件(1,2,2)A、B、C三个贡献值分别为-3、-1、-1三个calc返回值都是0输出-1符合预期。第二个边界是贡献值恰好为0的情况。比如事件(3,2,1)A的贡献值是0。如果此时sum已经大于0那么加上这个0之后sum仍然大于0所以这个事件可以选因为它不影响胜利局面还能增加事件数量。如果sum本来是0加上0之后sum还是0不满足严格大于不能选。这个逻辑完全由“sum 0才cnt否则break”控制等于说遇到0时要看当时sum的状态。第三个边界是全部事件对三个国家都是负贡献或零贡献。这种情况下三个calc返回的都是0最终输出-1。要注意这里的判断条件是ans 0而不是cnt 0因为只要有一个国家能凑出至少一个事件答案就至少是1不会出现负值。4.3 自己造几组数据验证竞赛里写完代码后最好自己构造几组小数据人工验算。我常用的套路是先写一个二进制枚举的暴力程序再和贪心算法对拍。举几个典型例子输入 3 1 2 2 2 3 2 2 0 3全选是A5B5C7C并不大于AB10。选第1和第3个A3B2C5C大于AB5吗等于不满足。选第2和第3个A4B3C5C不大于7。选第3个单独一个A2B0C3C大于2成立。所以答案是1。算法里C国的贡献值分别是2-1-2-1、2-2-3-3、3-2-01排序后是1、-1、-3累加1后cnt1再加-1变成0停止返回1。正确。再试一组有多个正贡献的输入 4 5 0 0 4 1 1 1 1 1 2 2 2A的贡献值是5、2、-1、-2排序后5、2、-1、-2累加5则cnt1加2后sum7则cnt2加-1后sum6则cnt3加-2后sum4则cnt4所以A能全选4个事件。验证全选A12B4C4A大于8成立。这种“赢家优势足够大以至于所有负贡献事件都能被消化”的情况最容易看出贪心是否写对。5. 常见错误与排查技巧实录5.1 错误一只累加正数把负数全扔掉我见过很多版本是排序后只取w[i] 0的数累加然后返回正数的个数。这个写法在小数据上偶尔能过但一遇到我前面举的例子就会错。比如A的贡献值是5、-1只取正数的话答案是1但正确贪心是先加5再加-1sum4仍然大于0答案应该是2。负数不是不能选只要当前sum够厚选进去不减反增事件数量。判断要不要选某个负数关键看加上它之后sum是否仍然大于0。通俗理解就是正贡献是“本金”负贡献是“开销”只要花完之后积蓄还是正的这笔开销就是划算的因为它帮你多凑了一个事件数量。5.2 错误二排序方向反了如果把贡献值从小到大排序那第一个数就是最小值sum大概率一开始就被打到0以下然后直接break答案变成0或者很小的数。排查这个问题最快的方法是打印排序后的w数组肉眼看一下是不是降序。C里用greater ()Java里用Collections.reverseOrder()Python里用reverseTrue这三个写法分别对应三种语言记混了就会出现方向错误。这里还有一个细节如果贡献值数组里存在大量相同的值排序方向错乱时不容易被样例发现因为结果可能在某些数据下碰巧相同。所以不要只看一组数据要多用随机数据对拍。5.3 错误三sum恰好为0时继续累加题目要求严格大于所以sum等于0的时候当前这个事件不能算作胜利事件而且根据排序后的性质后面的值只会更小sum也不可能再转正必须立刻break。有些同学在这里写成了sum 0导致把恰好持平的情况也算成胜利答案偏大。这个错误相当隐蔽因为只有在贡献值组合出恰好为0时才会触发。自测时专门构造一个sum恰好归零的数据跑一遍就能避开这个坑。5.4 错误四类型溢出C里如果a、b、c数组开intw[i] a[i] - b[i] - c[i]这一步就已经可能溢出因为a、b、c每个最大1e9相减后最小是-2e9接近int下限。更严重的是累加sum最大值可能到1e14int完全装不下。这类问题用long long能直接解决但要注意vector 和sort的greater ()类型匹配不然编译阶段就会报错。Java里long是64位不会溢出但要小心读入用nextLong而不是nextInt。5.5 常见问题速查表错误现象可能原因排查方法结果比正确答案小很多只累加了正贡献忽略了可选的负贡献改成从大到小连续累加sum 0就继续结果比正确答案大把等于0的情况也算胜利把条件改成sum 0严格大于答案一直是0或-1排序方向反了最小值在最前面打印w数组检查降序大数据下运行报错int溢出或数组越界全部用long/long long检查数组长度Java排序报错用long[]直接传Collections.reverseOrder转成Long[]再排序样例能过但提交不对可能问题出在“任意挑选”的细节用二进制枚举写暴力程序对拍5.6 一个实用的对拍思路对拍是竞赛里最可靠的验证手段。你可以用Python写一个递归枚举所有子集的暴力版本对任意n 15随机生成数据然后让暴力版本和贪心版本跑同样的输入比较输出。一旦发现不一致就缩小n把出错的测试数据打出来手动分析。这个方法能覆盖绝大多数边界情况比自己凭空构造数据要全面得多。对拍的代码不复杂但我在实际备赛过程中发现很多同学宁可盯着屏幕看半天也懒得写对拍这其实是效率最低的排错方式。6. 这类题背后的通用套路6.1 “枚举赢家”加“差分排序”的模型识别如果只把《三国游戏》当成一道独立题目那你学到的东西很有限。但如果你把它作为一个模型记下来后面能省很多思考时间。这个模型的识别特征很明确题目给你若干个“事件”或“物品”每个会给多个维度增加数值你要求的是“选尽可能多的事件使某个维度严格超过其他维度总和”。只要是这种结构思路基本都是固定三段式第一枚举最终赢家第二把所有维度压成一个差分值第三排序后贪心累加。这个套路在蓝桥杯里出现过不止一次。它本质上是一种“先定胜负再算净收益”的博弈简化思维把多条件比较变成单条件比较。实际做题时你可以先条件反射地试试能不能枚举获胜方再看每个事件对获胜方的净贡献如果这两个步骤都能走通那这道题大概率就是排序贪心。6.2 和CSP、GESP等竞赛题的横向对比最近几年CSP-J/S、GESP这类考试里也频繁出现“给定多组增量求满足某个比较关系的最大选择数”的题目。它们不一定叫三国游戏但底层思路几乎都是差分加贪心。比如“小苹果”“积木大赛”这类题新手看起来是模拟老手一眼就能看出有贪心结构。再比如CSP-S级别的某些题目会把这种“枚举赢家”扩展成“枚举参数之后二分答案”核心还是差分思想。所以我的建议是做真题不要只背题解要把同一类题放在一起横向比较。你刷完《三国游戏》之后再去做几个“物品选择最大化”的题试着找出它们共用的转化手法这样以后再遇到新题即使是包装成游戏背景也能很快识别出题人的考查点。6.3 比赛中的做题节奏建议如果是正式比赛遇到这种题建议按这个节奏来。前5分钟读题加手算样例确定它属于差分贪心模型接着用10到15分钟想清楚排序后break的边界然后写代码加测试整个过程控制在30到40分钟以内。如果卡了超过20分钟还没思路就先去做后面的题回头再拿剩余时间补。蓝桥杯省赛B组的题目量不小时间分配比单题死磕更重要一道题卡太久会影响整场心态。写代码时先不要追求炫技用最容易理解的方式把主体逻辑写出来跑通了再考虑优化。像《三国游戏》这种题最朴素的写法就是最优解没必要画蛇添足。还有一点经验是所有涉及long long的地方从一开始就用long long别等溢出报错再回头改那样反而更浪费时间。最后再分享一个我在实际刷题中总结的小技巧。遇到这种“选择若干事件使某条件成立并让数量最多”的题先不要急着想数据结构先问自己三个问题能不能枚举获胜者每个事件能不能压缩成单个贡献值排序后前缀和是否具有单调性这三个问题都能回答“是”那基本就是排序贪心直接写就行了。这个思路帮我解决过不少看似复杂的题目希望也能帮你减少一些比赛中的试错成本。