目录
题目
小蓝正在玩一款游戏。
游戏中魏蜀吴三个国家各自拥有一定数量的士兵 X,Y,Z（一开始可以认为都为 00）。
游戏有 n 个可能会发生的事件，每个事件之间相互独立且最多只会发生一次，当第 i 个事件发生时会分别让 X,Y,Z 增加 Ai,Bi,Ci。
当游戏结束时 (所有事件的发生与否已经确定)，如果 X,Y,Z 的其中一个大于另外两个之和，我们认为其获胜。
例如，当 X>Y+Z 时，我们认为魏国获胜。
小蓝想知道游戏结束时如果有其中一个国家获胜，最多发生了多少个事件?
如果不存在任何能让某国获胜的情况，请输出
−1。输入格式
输入的第一行包含一个整数 n。
第二行包含 n 个整数表示 Ai，相邻整数之间使用一个空格分隔。
第三行包含 n 个整数表示 Bi，相邻整数之间使用一个空格分隔。
第四行包含 n 个整数表示 Ci，相邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 40%40% 的评测用例，n≤500；
对于 70%70% 的评测用例，n≤5000；
对于所有评测用例，1≤n≤10^5，0≤Ai,Bi,Ci≤10^9。
注意，蓝桥杯官方给出的关于 Ai,Bi,Ci 的数据范围是 1≤Ai,Bi,Ci≤10^9，但是这与给出的输入样例相矛盾，因此予以纠正。输入样例：
3 1 2 2 2 3 2 1 0 7输出样例：
2样例解释
发生两个事件时，有两种不同的情况会出现获胜方。
发生 1,21,2 事件时蜀国获胜。
发生 1,31,3 事件时吴国获胜。
思路
我先做这个题，第一反应是01背包动态规划问题
（因为题意：一个事件有选或不选两种选择，但是发现不可用，
其一是因为有三个国家，那就需要考虑三种情况，
其二，根据DP分析无法判断，例如，如果我们在判断魏国兵力，如果某个事件的魏国兵力<另外两个国家的兵力之和，无法判断选上该事件后后续能否保证兵力能够大于其他两个国家，但是题目又是求最大事件数）
分析之后我尝试记录三个国家分别的情况，使用数组a[ ],b[ ],c[ ]记录选完事件后，每个国家剩余的兵力数，发现仍然存在上述第二种不可用的情况。
那为什么在每次遍历到事件的时候再进行相加判断呢？我们可以提前将三个国家的所有的事件的兵力进行相减之后，存储每个国家剩余的兵力（可以为负）。意思就是，比如说魏国，我们就用a[ ] 存储每个事件的魏国的兵力-其他两个国家的兵力。其余两种情况同理。
每个国家想要达到自己国家胜利，即选择完事件后剩余的兵力大于0，选择是无关的，意思是，每个国家都可以随意挑选事件，之间相互独立，没有制约，只是都在追求让自己国家的兵力更多（比如魏国挑选事件1，蜀国也可以选事件1，只是剩余的兵力数不相同）。
因此，我们可以对提前求解出来的每个事件每个国家剩余的兵力数进行从大到小排序，因此我们只需要从头进行选择，从而选择出最长一段距离的最大事件数。没有第二种不可用情况的困扰。
这个思路主要就是贪心（太菜了，证明不了），最后选择事件就是对三种情况所有计算出的剩余兵力的枚举，最多选择多少个可以满足条件。（二分可以优化，但是没必要，因为还要处理前缀和）
代码
代码很糙
import java.io.*;
import java.util.*;
import java.lang.*;
// 大于某个值的时候，要减一个里面最小的数
class Main{
static int N = 100010;
static int n;
static int[] a = new int[N]; // 存储魏国在事件i中的兵力
static int[] b = new int[N]; // 存储蜀国在事件i中的兵力
static int[] c = new int[N]; // 存储吴国在事件i中的兵力
public static void main(String[] args) throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(in.readLine()); // 事件总数
// 因为java使用Collections.reverseOrder()完成从大到小排序，需要使用对应的类，而不是基本类型，因此这里我重开三个数组
Integer[] a1 = new Integer[n]; // a-b-c
Integer[] b1 = new Integer[n]; // b-a-c
Integer[] c1 = new Integer[n]; // c-a-b
// 根据输入读取事件
String[] s = in.readLine().split(" ");
for(int i=0;i<n;i++) a[i] = Integer.parseInt(s[i]);
s = in.readLine().split(" ");
for(int i=0;i<n;i++) b[i] = Integer.parseInt(s[i]);
s = in.readLine().split(" ");
for(int i=0;i<n;i++) {
c[i] = Integer.parseInt(s[i]);
// 计算每个国家每个事件下剩余兵力数
a1[i] = a[i]-b[i]-c[i];
b1[i] = b[i]-a[i]-c[i];
c1[i] = c[i]-a[i]-b[i];
}
// 对每个国家每个事件剩余的兵力数从大到小排序
Arrays.sort(a1,Collections.reverseOrder());
Arrays.sort(b1,Collections.reverseOrder());
Arrays.sort(c1,Collections.reverseOrder());
long sum1 = 0,sum2 = 0, sum3 = 0; // 可能会爆int，枚举过程中记录当前选择的所有事件下剩余的兵力数
int res1 = 0,res2 = 0, res3 = 0; // 每个国家能选择的最多的事件数
for(int i=0;i<n;i++){
// 魏
if(sum1+a1[i]>0){ // 选过的事件剩余兵力数+当前事件剩余兵力数大于0才可以
res1 += 1;
sum1 = sum1+a1[i];
}
// 蜀
if(sum2+b1[i]>0){
res2 += 1;
sum2 = sum2+b1[i];
}
// 吴
if(sum3+c1[i]>0){
res3 += 1;
sum3 = sum3+c1[i];
}
}
int res = Math.max(res1,res2);
res = Math.max(res,res3);
if(res==0) System.out.println(-1);
else System.out.println(res);
}
}
