思路:
题目说明三个国家中某一个获胜时,所需要的最大次数。
将情况分解,分为A、B、C国家获胜时的情况的最大值。然后三个国家的值求max。
先考虑A国家获胜的情况。
错误记录:
1.栈空的时候没有想到,因为总和的数可能一直是正数,即A-B-C一直大于0,导致一直在循环
2.数据范围超出int,导致数据溢出
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<unordered_map>
using namespace std;
const int N = 1E5+10;
long long a[N],b[N],c[N];
priority_queue<long long> wa,wb,wc;
int main (){
int n;cin>>n;
for(int i =1 ;i<=n;++i){
scanf("%lld",&a[i]);
}
for(int i =1 ;i<=n;++i){
scanf("%lld",&b[i]);
}
for(int i =1 ;i<=n;++i){
scanf("%lld",&c[i]);
}
long long sum = 0;
//计算A国胜利的最大次数
int numa = 0;
for(int i =1 ;i<=n;++i){
wa.push(a[i]-b[i]-c[i]);
}
sum = wa.top();wa.pop();
numa++;
while(sum>0&&!wa.empty()){
sum+=wa.top();wa.pop();
numa++;
}
if(sum<=0)
numa--;
//计算B国胜利的最大次数
int numb = 0;
sum = 0;
for(int i =1 ;i<=n;++i){
wb.push(b[i]-a[i]-c[i]);
}
sum = wb.top();wb.pop();
numb++;
while(sum>0&&!wb.empty()){
sum+=wb.top();wb.pop();
numb++;
}
if(sum<=0)
numb--;
//计算C国胜利的最大次数
int numc = 0;
sum = 0;
for(int i =1 ;i<=n;++i){
wc.push(c[i]-a[i]-b[i]);
}
sum = wc.top();wc.pop();
numc++;
while(sum>0&&!wc.empty()){
sum+=wc.top();wc.pop();
numc++;
}
if(sum<=0)
numc--;
int maxn = max(numa,numb);
maxn = max(maxn,numc);
if(maxn==0)cout<<-1<<endl;
else cout<<maxn<<endl;
return 0;
}