题目链接

题意解读

有n个人，每个人要去3个部门中的一个，但是每一个部门最多容纳n/2个人。每个人到各个部门有一定美好值，求最大美好值总和

思路

对于每一个人，求这个人去每一个部门的最大美好值和次大美好值。
Q1 为什么要求最大美好值和次大美好值？
A1 如果某一个部门爆满了，就找一个合适的部门让该部门的人转移过去，并保证损失最小
Q2 该存最小损失呢，怎么办呢
A2 想想有什么办法可以一直往里面放东西还一直返回最小的？优先队列成为首选
Q3 现在知道怎么存，怎么求呢？
A3 就用每一个人去各个部门的最大美好值-次大美好值

代码参考

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int t;
int n;
long long a[200005][6];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);//添加快读可以减少200ms的运行时间
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=3;j++){
                cin>>a[i][j];//input
            }
        }
        long long ans=0;
        priority_queue<long long ,vector<long long>,greater<long long>>q[4]; //每一个部门都需要算最小损失，此处q的空间要开够！
        for(int i=1;i<=n;i++){
            a[i][4]=-100000000;
            int mx=0,mx2=4;
            for(int j=1;j<=3;j++){
                if(a[i][j]>a[i][mx]){
                    mx2=mx;  //计算最大次大
                    mx=j;
                }else if(a[i][j]>a[i][mx2]){
                    mx2=j;
                }
            }
            q[mx].push(a[i][mx]-a[i][mx2]);
            ans+=a[i][mx];
        }
        for(int i=1;i<=3;i++){
            while(q[i].size()>n/2){
                ans-=q[i].top();//减去最小损失
                q[i].pop();
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

总结

这道题用贪心的策略，用优先队列维护。
教会我们：从最大总和的组成来考虑，比如这道题是最大美丽值总和=所有人都选最大美丽值部门的美丽值和-部门饱满后得要踢走的人里美丽值损失最小。依旧长难句

警钟敲烂

空间记得开够！