三国游戏(贪心 排序)

三国游戏

利用贪心、排序、前缀和的计算方法，特别注意不要数据溢出了，sum 加long long

s[i] = x[i]-y[i]-z[i]

输入:

3
1 2 2
2 3 2
1 0 7

输出:

2

#include <bits/stdc++.h>
using namespace std;const int N = 1e5+100;typedef long long ll;bool cmp(int x,int y)
{return x>y;
}int a[N],b[N],c[N];
int s[N];
int n;int get_ans(int x[],int y[],int z[])
{int ans = 0;ll sum = 0;//memset(s,0,sizeof(s));for(int i=1;i<=n;i++){s[i] = x[i]-y[i]-z[i];}sort(s+1,s+n+1,cmp);for(int i=1;i<=n;i++){sum+=s[i];if(sum>0) ans++;else break;}if(ans == 0) return -1;return ans;
}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_a = get_ans(a,b,c);int ans_b = get_ans(b,a,c);int ans_c = get_ans(c,a,b);int ans = max(ans_a,max(ans_b,ans_c));printf("%d\n",ans);return 0;
}

Debug: