蓝桥杯刷题-09-三国游戏-贪心⭐⭐⭐

蓝桥杯2023年第十四届省赛真题-三国游戏

小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵X, Y, Z (一开始可以认为都为 0 )。游戏有 n 个可能会发生的事件，每个事件之间相互独立且最多只会发生一次，当第 i 个事件发生时会分别让 X, Y, Z 增加Ai , Bi ,Ci 。
当游戏结束时 (所有事件的发生与否已经确定)，如果 X, Y, Z 的其中一个大于另外两个之和，我们认为其获胜。例如，当 X > Y + Z 时，我们认为魏国获胜。小蓝想知道游戏结束时如果有其中一个国家获胜，最多发生了多少个事件?
如果不存在任何能让某国获胜的情况，请输出 −1 。

#include <iostream>
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n;
int cal_ans(vector<int>&a,vector<int>&b,vector<int>&c)
{vector<int>tmp(n);int sum=0;for(int i=0;i<n;i++)tmp[i]=a[i]-(b[i]+c[i]);sort(tmp.begin(),tmp.end());int cnt=0;for(int i=n-1;i>=0;i--){if(sum+tmp[i]>0){sum+=tmp[i];cnt++;}elsebreak;}return cnt;
}
void solve()
{cin>>n;vector<int>a(n),b(n),c(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 ans=0;ans=cal_ans(a,b,c);ans=max(ans,cal_ans(b,a,c));ans=max(ans,cal_ans(c,a,b));if(ans)cout<<ans<<endl;elsecout<<-1<<endl;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;while(t--)solve();}