卡了2个小时（真的）

祝大家CSP rp++

我这贪心卡了这么久其实是学贪心时C++上还没开智
正题：只要一个正常的最优分组。如果有一组人数>n/2，则让sum-最小的第一想去和第二想去的差值的前ma-n/2个差值,即是最终答案；反之，则输出sum。

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct o{
	int x,y,z;
}a[100010];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	int T;
    cin >> T;
	while(T--){
        int n,cnt1=0,cnt2=0,cnt3=0;
        cin >> n;
        ll sum=0;
        for(int i=1;i<=n;i++){
            cin>>a[i].x>>a[i].y>>a[i].z;
            //最优分组
            int maxx=0;
            sum+=max(a[i].x,max(a[i].y,a[i].z));
            maxx = max(a[i].x,max(a[i].y,a[i].z));
            if(a[i].x>a[i].y&&a[i].x>a[i].z)cnt1++;
            else if(a[i].y>a[i].z)cnt2++;
            else cnt3++;
        }
        int ma = 0;
        ma = max(cnt1,max(cnt2,cnt3));
        if(ma<=(n/2)){
            //输出sum。
            cout << sum << "\n";
        }
        else{
            //如果有一组人数>n/2，则让sum-最小的第一想去和第二想去的差值的前/ma-n/2个差值
            priority_queue<int,vector<int>,greater<int>>q;
            if(cnt1>(n/2)){
                for(int i=1;i<=n;i++){
                    if(a[i].x<=max(a[i].y,a[i].z))continue;
                    //这里必须是a[i].x<=max(a[i].y,a[i].z),否则卡5个测试点
                    q.push(a[i].x-max(a[i].y,a[i].z));
                }
            }
            if(cnt2>(n/2)){
                for(int i=1;i<=n;i++){
                    if(a[i].y<max(a[i].x,a[i].z))continue;
                    q.push(a[i].y-max(a[i].x,a[i].z));
                }
            }
            if(cnt3>(n/2)){
                for(int i=1;i<=n;i++){
                    if(a[i].z<max(a[i].y,a[i].x))continue;
                    q.push(a[i].z-max(a[i].x,a[i].y));
                }
            }
            for(int i=1;i<=ma-n/2;i++){
                sum-=q.top();
                q.pop();
            }
            cout << sum << "\n";
        }
    }
    return 0;
}

点赞