三国游戏（第十四届蓝桥杯）
题目
小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵 X,Y,Z（一开始可以认为都为 0）。
游戏有 n个可能会发生的事件，每个事件之间相互独立且最多只会发生一次，当第 i个事件发生时会分别让 X,Y,Z
增加 A i , B i , C i A_i,B_i,C_i Ai,Bi,Ci。
当游戏结束时 (所有事件的发生与否已经确定)，如果 X,Y,Z的其中一个大于另外两个之和，我们认为其获胜。
例如，当 X>Y+Z时，我们认为魏国获胜。
小蓝想知道游戏结束时如果有其中一个国家获胜，最多发生了多少个事件?
如果不存在任何能让某国获胜的情况，请输出 −1。
输入格式
输入的第一行包含一个整数 n。
第二行包含 n个整数表示 A i A_i Ai，相邻整数之间使用一个空格分隔。
第三行包含 n个整数表示 B i B_i Bi，相邻整数之间使用一个空格分隔。
第四行包含 n 个整数表示 C i C_i Ci，相邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 40%的评测用例，n≤500；
对于 70%的评测用例，n≤5000；
对于所有评测用例， 1 ≤ n ≤ 1 0 5 ， 0 ≤ A i , B i , C i ≤ 1 0 9 1≤n≤10^5，0≤A_i,B_i,C_i≤10^9 1≤n≤105，0≤Ai,Bi,Ci≤109。
注意，蓝桥杯官方给出的关于 A i , B i , C i A_i,B_i,C_i Ai,Bi,Ci
的数据范围是 1 ≤ A i , B i , C i ≤ 1 0 9 1≤Ai,Bi,Ci≤10^9 1≤Ai,Bi,Ci≤109，但是这与给出的输入样例相矛盾，因此予以纠正。
输入样例：
3
1 2 2
2 3 2
1 0 7
输出样例：
2
样例解释
发生两个事件时，有两种不同的情况会出现获胜方。
发生 1,2 事件时蜀国获胜。
发生 1,3 事件时吴国获胜。
代码(python版本)
n=int(input())
def check(x,y,z)->int:w=[]for i in range(n):w.append(x[i]-y[i]-z[i])w.sort(reverse=True)res=-1sum=0for i in range(n):sum+=w[i]if sum>0:res=i+1return res
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
print(max(check(a,b,c),check(b,a,c),check(c,a,b)))
代码（cpp版本）
代码先欠着
思路：
本题是一道贪心题。当我一开始看这个题目的时候，首先想到的就是一道dfs题，但是当我看到数据范围为 1 0 5 10^5 105的时候我直接人傻，这还怎么dfs。于是换一个思路。
首先因为这个数据范围是 1 0 5 10^5 105,那么我们需要将时间复杂度控制在 n l o g n nlogn nlogn中。
本题要求的是一个国家打赢两个国家最多能发生多少次事件，看到最多，我就感觉是一道贪心题，那么怎么贪心呢？
首先我们需要想明白怎么贪？那我们可以先假设三个国家分别是ABC，然后我们假设 A > B + C A>B+C A>B+C,那么ABC到底是哪三个国家呢？这个直接可以枚举出来，A是魏蜀吴三个其中之一，剩下的B和C就是除了A以外的两个国家。
那么我们可以写一个函数来判断 A > B + C A>B+C A>B+C最多能要多少次
那么我们可以遍历ABC三个数组，然后用一个数组W来接受一下A国和B+C国的兵力差，也就是W[i]=A[i]-B[i]-C[i]的值，那么W[i]的含义是什么呢？很明显当W[i]>0的时候说明A的兵力比B+C的要多，这个事件我们当然要选。然后进行排序，接下来就是每次都获取到当前的兵力。然后用一个sum来记录，sum代表的是什么意思呢，就是A当前比B+C多sum个兵，然后我们依次进行遍历，sum不断累加W[i]，当sum累加当前的兵力之后还是大于零，说明当前的事件容许发生，这时候就该让res++了。直到sum小于0的时候就不行了。
然后我们来看这个思路，整个的时间复杂度正好是 n l o g n nlogn nlogn(sort的时间复杂度)。
最后我们只需要调用上面的函数三次即可，也就是check(魏，蜀，吴)，check(蜀，魏，吴)，check(吴，蜀，魏)，然后三者取最大值就行。