一、题目
1、原题链接
2、题目描述
二、解题报告
1、思路分析
思路参考y总：y总讲解视频
（1）题目中的获胜情况分为三种：魏国胜（兵量为X）、蜀国胜（兵量为Y）、吴国胜（兵量为Z）。以魏国胜为例，需要使得X>Y+Z，也就是需要使得X-Y-Z>0，记W=X-Y-Z，即W>0，W初始为0（因为X、Y、Z初始均为0）。
（2）由于每个事件都会使X，Y，Z分别增加A[i]、B[i]、C[i]。记V[i]=A[i]-B[i]-C[i]，即每个事件会使W增加V[i]。所以题目就可以转化为最多多少个事件（也就是对W加最多多少次不同的V[i]）可以使W保持大于0（也就是这些事件的每个V[i]之和大于0）。
（3）可以将V数组进行从大到小排序，由于W初始为0，所以当发生V[i]>0的事件发生最多的情况下发生的事件最多的情况为最优解。所以大到小依次枚举V[i]，并同时记录当前发生事件数和到目前枚举到的V[i]之和，若出现总和不大于0时，说明此时已经不是最优解，最优解即为除去当前事件，前面所有事件均发生的情况。
（4）依据相同思路，依次求出蜀国、吴国获胜时的最大发生事件数，取最大值即可，若不存在让任何一国获胜的情况，按题目要求输出即可。
2、时间复杂度
时间复杂度为O(n)
3、代码详解
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N], b[N], c[N];
int v[N];
bool cmp(int A ,int B) {
return A > B;
}
//x[]为获胜国的事件产生效果，y[]、z[]为未获胜国的
int solve(int x[], int y[], int z[]) {
for (int i = 0; i < n; i++) {
v[i] = x[i] - y[i] - z[i];
}
sort(v, v + n, cmp);
//注：可能会超int
long long sum = 0, cnt = 0; //sum记录当前枚举到V[i]的总和,cnt记录发生事件数
for (int i = 0; i < n; i++) {
sum += v[i];
if (sum > 0) cnt++;
else break;
}
return cnt;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
for (int i = 0; i < n; i++) cin >> c[i];
int res = 0;
int num1 = solve(a, b, c);
int num2 = solve(b, a, c);
int num3 = solve(c, a, b);
//取三种情况最大值
res = max(max(num1, num2), num3);
if (res) cout << res;
else cout << -1; //若不存在，则输出-1
return 0;
}
