拿今年蓝桥杯省赛的《三国游戏》来说，它表面上是一道模拟三国对抗的题目，实际上考的是贪心加排序，属于竞赛里非常典型的“转化后求最优”问题。很多同学第一次看到它，第一反应是去枚举所有事件组合，结果发现n一上来就是10的5次方量级，直接傻眼。这道题的精髓在于：先把“哪个国家赢”这件事拆开，再把每个事件对胜利局面的贡献算成一个数，最后用排序加前缀和解决。这篇文章我会从暴力思路讲起，把贪心为什么可行、代码怎么写、容易踩哪些坑全部讲透，无论你是准备蓝桥杯Java组、C++组还是Python组，这套思路都能直接照搬。
1. 题目到底在问什么
1.1 先读清楚题面
题面大意是这样的：有A、B、C三个国家，初始兵力都是0。现在有n个事件，每个事件会给三个国家分别增加一定的兵力。你可以从这n个事件中任意挑选若干个执行，问最多能挑多少个事件，使得执行完这些事件之后，存在一个国家，它的兵力严格大于另外两个国家兵力之和。如果无论如何都不存在这样的方案，输出-1。
这句话里有几个要点值得圈出来。第一是“任意挑选”，意味着顺序无所谓，你可以跳过一些事件，这本质上是一个子集选择问题。第二是“严格大于”，也就是胜利国的兵力要大于另外两国的兵力相加，等于都不行，这一点在写代码时非常容易忽略。第三是“最多能挑多少个事件”，不是问你能不能让某个国家赢，而是问在保证能赢的前提下，事件数量要最大化。
我用一组自己手造的数据来演示。假设n=4，四个事件分别给三国增加的兵力是：
4 1 1 2 5 2 1 2 6 3 3 1肉眼看一下，如果全选，A的总兵力是4+2+1+3=10，B是1+5+2+3=11，C是1+2+6+1=10。B虽然最高，但B=11并没有大于A+C=20，所以全选不是一个胜利方案。如果只选第1个和第4个事件，A=4+3=7，B=1+3=4，C=1+1=2，此时A=7大于B+C=6，A国获胜，事件数是2。我还可以继续试着加事件吗？再加第2个事件，A=9，B=9，C=4，A不大于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[i+1] <= w[i]，那么sum + w[i+1] <= sum + w[i] <= 0，后面的所有值加起来只会让sum更小。也就是说，从第i个事件开始，之后的所有事件都已经不可能让前缀和重新回到正数了。这个性质正是排序贪心成立的依据，也是这题最关键的一步证明。
再回到刚才的数据。A的四个dA排序后是2, -1, -5, -7。累加第一个2，sum=2大于0，事件数记为1。累加第二个-1，sum=1仍然大于0，事件数记为2。累加第三个-5，sum=-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 vector<ll>& x, const vector<ll>& y, const vector<ll>& z) { int n = x.size(); vector<ll> w(n); for (int i = 0; i < n; i++) { w[i] = x[i] - y[i] - z[i]; } sort(w.begin(), w.end(), greater<ll>()); 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; vector<ll> 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(reverse=True)。要注意的是千万不能用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(reverse=True) 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 边界情况逐个过
边界测试是竞赛里保命的关键。第一个边界是n=1。如果那一个事件本身就能让某个国家严格大于另外两国之和，那答案就是1，否则就是-1。用算法跑一遍，比如只有一个事件(5,2,2)，A的贡献值是5-2-2=1，排序后累加为1，大于0，cnt=1，答案就是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全选是A=5，B=5，C=7，C并不大于A+B=10。选第1和第3个，A=3，B=2，C=5，C大于A+B=5吗？等于，不满足。选第2和第3个，A=4，B=3，C=5，C不大于7。选第3个单独一个，A=2，B=0，C=3，C大于2，成立。所以答案是1。算法里C国的贡献值分别是2-1-2=-1、2-2-3=-3、3-2-0=1，排序后是1、-1、-3，累加1后cnt=1，再加-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则cnt=1，加2后sum=7则cnt=2，加-1后sum=6则cnt=3，加-2后sum=4则cnt=4，所以A能全选4个事件。验证全选：A=12，B=4，C=4，A大于8，成立。这种“赢家优势足够大，以至于所有负贡献事件都能被消化”的情况，最容易看出贪心是否写对。
5. 常见错误与排查技巧实录
5.1 错误一：只累加正数，把负数全扔掉
我见过很多版本是排序后只取w[i] > 0的数累加，然后返回正数的个数。这个写法在小数据上偶尔能过，但一遇到我前面举的例子就会错。比如A的贡献值是5、-1，只取正数的话答案是1，但正确贪心是先加5，再加-1，sum=4仍然大于0，答案应该是2。负数不是不能选，只要当前sum够厚，选进去不减反增事件数量。
判断要不要选某个负数，关键看加上它之后sum是否仍然大于0。通俗理解就是：正贡献是“本金”，负贡献是“开销”，只要花完之后积蓄还是正的，这笔开销就是划算的，因为它帮你多凑了一个事件数量。
5.2 错误二：排序方向反了
如果把贡献值从小到大排序，那第一个数就是最小值，sum大概率一开始就被打到0以下，然后直接break，答案变成0或者很小的数。排查这个问题最快的方法是打印排序后的w数组，肉眼看一下是不是降序。C++里用greater ()，Java里用Collections.reverseOrder()，Python里用reverse=True，这三个写法分别对应三种语言，记混了就会出现方向错误。
这里还有一个细节：如果贡献值数组里存在大量相同的值，排序方向错乱时不容易被样例发现，因为结果可能在某些数据下碰巧相同。所以不要只看一组数据，要多用随机数据对拍。
5.3 错误三：sum恰好为0时继续累加
题目要求严格大于，所以sum等于0的时候，当前这个事件不能算作胜利事件，而且根据排序后的性质，后面的值只会更小，sum也不可能再转正，必须立刻break。有些同学在这里写成了sum >= 0，导致把恰好持平的情况也算成胜利，答案偏大。这个错误相当隐蔽，因为只有在贡献值组合出恰好为0时才会触发。自测时专门构造一个sum恰好归零的数据跑一遍，就能避开这个坑。
5.4 错误四：类型溢出
C++里如果a、b、c数组开int，w[i] = a[i] - b[i] - c[i]这一步就已经可能溢出，因为a、b、c每个最大1e9，相减后最小是-2e9，接近int下限。更严重的是累加sum，最大值可能到1e14，int完全装不下。这类问题用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，别等溢出报错再回头改，那样反而更浪费时间。
最后再分享一个我在实际刷题中总结的小技巧。遇到这种“选择若干事件使某条件成立并让数量最多”的题，先不要急着想数据结构，先问自己三个问题：能不能枚举获胜者？每个事件能不能压缩成单个贡献值？排序后前缀和是否具有单调性？这三个问题都能回答“是”，那基本就是排序贪心，直接写就行了。这个思路帮我解决过不少看似复杂的题目，希望也能帮你减少一些比赛中的试错成本。
