沉浸于简单题无法自拔
大概思路:
我们从获胜国相交其余两国的兵力的增减量出发,
比如我们现在想让魏国赢,这组数据是3 2 1,表示魏国+4,蜀国+2,吴国+1,魏国的改变量为1(3-(2+1))
然后再将这组改变量的数据排序,如果是降序排序的话,(普遍情况下)
- 前几项都是增幅该国,为了发生数最多,显然都要取
- 再几项,可能已经是让兵力亏损了,但还是能保证该国胜利,所以也要取
- 发现亏损太多了,连胜利都胜利不了了,直接停止循环返回发生数即可。
小tips
- 答案要的可是最大值,不要惯性思维
- 注意输入时,是按a1,a2,a3……b1,b2,b3……c1,c2,c3的顺序输入的
max({1,2,3,100,1000})
这样max可以同时求多个数的最大值
然后直接看代码的注释吧↓
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N], b[N], c[N];
int w[N]; //用于存储当前国家在各情况下兵力的改变量,所以即使为负,总量也可能比其他两国大(会用三次保存三个国家)
int work(int x[], int y[], int z[]) //x是获胜方
{
for(int i = 0;i<n;i++) w[i] = x[i] - y[i] - z[i]; // ex. x3 y1 z2表示魏增3,蜀增2,吴增2,但是w为0
sort(w, w + n, greater<int>()); //降序排序
//这样前几项正常情况下都是增加x国的战力。且为了发生数最多是一定同时发生的
int res = 0; //表示可发生的事件数
long long temp = 0; //表示现存兵力的差距(并不直接等价与总兵力,而是相较其它两国兵力变化之和的变化),只要大于0表示能赢
for (int i = 0; i < n; i++)
{
temp += w[i]; //再次强调这里的w是改变量,即使增量为负,但是为了发生事件数最多,在能赢的情况下也要选。
if (temp > 0) res++; //这个情况可以发生!
else break; //w是降序的,temp初始又是0,越循环只会越小
}
return res;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n; i++) scanf("%d", &b[i]);
for (int i = 0; i < n; i++) scanf("%d", &c[i]);
int res = max({ work(a,b,c),work(b,a,c),work(c,a,b) });
res = res ? res : -1; //题目要求,没有赢家(即res==0)时,输出-1
printf("%d\n", res);
return 0;
}