蓝桥集训之三国游戏

蓝桥集训之三国游戏

• 核心思想：贪心

  • 将每个事件的贡献值求出 降序排序
  • 从大到小求和为正是即可

•   #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;
    }