好吃力的反悔贪心

反悔贪心
这个>n/2的条件看起来很唐（也就是说最多只有一个组别人会多）从这里入手
一开时都放到最想去的
然后
把踢到其他组里面代价（也就是这个人第一想去和第二想去的差值）最小的人牺牲给到其他组
sum减去代价即可
时间复杂度：TNlogN

#include <bits/stdc++.h>
using namespace std;
int t;
struct stu{int a,b,c,mx;};
int main(){
    cin>>t;
    while(t--){
        int n,sum=0,cnt1=0,cnt2=0,cnt3=0,mx=0;
        stu a[100010];
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i].a>>a[i].b>>a[i].c;
            sum+=max(a[i].a,max(a[i].b,a[i].c));
            if(a[i].a>a[i].b&&a[i].a>a[i].c) cnt1++,a[i].mx=1;
            else if(a[i].b>a[i].c) cnt2++,a[i].mx=2;
            else cnt3++,a[i].mx=3;
        }
        mx=max(cnt1,max(cnt2,cnt3));
        if(mx<=n/2){
            cout<<sum<<endl;
            continue;
        }
        else{
            vector<int>d;
            for(int i=1;i<=n;i++){
                if(cnt1>n/2&&a[i].mx==1) d.push_back(a[i].a-max(a[i].b,a[i].c));
                else if(cnt2>n/2&&a[i].mx==2) d.push_back(a[i].b-max(a[i].a,a[i].c));
                else if(cnt3>n/2&&a[i].mx==3) d.push_back(a[i].c-max(a[i].b,a[i].a));
            }
            sort(d.begin(),d.end());
            for(int i=0;i<mx-n/2;i++){sum-=d[i];}
            cout<<sum<<endl;
        }
    }
    return 0;
}

我是蒟蒻想了这么久原谅我
求赞