蓝桥集训之三国游戏
蓝桥集训之三国游戏
-
核心思想：贪心
- 将每个事件的贡献值求出 降序排序
- 从大到小求和为正是即可
-
#include <iostream>#include <cstring>#include <algorithm>using namespace std;typedef long long LL;const int N = 100010;int a[N],b[N],c[N];int n;int work(int x[],int y[],int z[]){int w[n];for(int i=0;i<n;i++){w[i] = x[i]-y[i]-z[i]; }//降序sort(w,w+n,greater<int>());int res=-1;LL sum=0;for(int i=0;i<n;i++){sum += w[i];if(sum>0) res = i+1;else break;}return res;}int main(){cin>>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 res=max({work(a,b,c),work(b,a,c),work(c,a,b)});cout<<res<<endl;return 0;}