题目描述
小蓝正在玩一款游戏。
游戏中魏蜀吴三个国家各自拥有一定数量的士兵 X,Y,Z(一开始可以认为都为 0)。
游戏有 n个可能会发生的事件,每个事件之间相互独立且最多只会发生一次,当第 i个事件发生时会分别让 X,Y,Z 增加 Ai,Bi,Ci。
当游戏结束时 (所有事件的发生与否已经确定),如果X,Y,Z的其中一个大于另外两个之和,我们认为其获胜。
例如,当 X>Y+Z时,我们认为魏国获胜。
小蓝想知道游戏结束时如果有其中一个国家获胜,最多发生了多少个事件?
如果不存在任何能让某国获胜的情况,请输出 −1。
输入格式
输入的第一行包含一个整数 n。
第二行包含 n个整数表示 Ai,相邻整数之间使用一个空格分隔。
第三行包含 n个整数表示 Bi,相邻整数之间使用一个空格分隔。
第四行包含 n个整数表示 Ci,相邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
样例
输入样例:
3
1 2 2
2 3 2
1 0 7
输出样例:
2
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int n;
int A[N], B[N], C[N], W[N];
/*
>>这道题我们很容易想到暴力的方法——利用排列组合的思想
比如拿样例说明:最初先选三个事件,判断有无获胜国家,如果没有,那么从三个里面选两个事件再判断...
而数据n最大10的五次方,利用排列组合思想在时间上是肯定跑不完的;
>>贪心改进后的过程
·首先我们可以把所有排列组合的方案分为三大类:1是让魏国(x)获胜,2是让蜀国(y)获胜,3是让吴国(z)获胜;
·而check函数就是判断让某国获胜的所有方案中选取事件数最大的,那么分别比较三次,看看哪国获胜的方案中
选取的事件数最大,当然如果谁都没法获胜,那就输出-1;
·暴力的排列组合思想行不通是因为对X>Y+Z这个信息理解的不够,首先X>Y+Z可以等价转换为X-Y-Z>0,为此我们
设一个W[]数组,它维护的就是每个事件如果发生,那么能使当前判断的某国获胜概率的贡献程度,如果>0那肯
定能增加该国获胜的概率,如果<=0那肯定会减少该国获胜的概率;
·接下来就是贪心思想了,我们将W[]数组从大到小排序,从头开始枚举,我们选择第一个w[1],它肯定n个当中
值最大的,这次枚举就是说明我如果只选择一个事件的话,那我就选这n个里面能让该国获胜做出最大贡献的就
行;因为我就是要判断一下这个国家能不能获胜,那就贪心的选择做出贡献越大,每次都尽量选做贡献最大的,
这样就避免了暴力思想中一些无用的判断;
·当然,回归题目要求,问如果有国家获胜,最多能选多少事件,所以在判断时,我们要找sum的临界值,也就是
如果>0,那说明这个事件可以选,继续往下走,如果<=0,那说明这个事件及其往后就不用再考虑了。
*/
int check(int x[], int y[], int z[]) {
for (int i = 1; i <= n; i++) {
W[i] = x[i] - y[i] - z[i];
}
sort(W + 1, W + n + 1, greater<int>());
int res = -1;
LL sum = 0;
for (int i = 1; i <= n; i++) {
sum += W[i];
if (sum > 0) res = i;
else break;
}
return res;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> A[i];
for (int i = 1; i <= n; i++) cin >> B[i];
for (int i = 1; i <= n; i++) cin >> C[i];
int ans = max({check(A, B, C), check(B, A, C), check(C, A, B)});
cout << ans;
return 0;
}