考场上前两分钟所有人开始打代码直接慌了。

首先，我们贪心把所有人都选择最满意的部门。

这样为什么不对？因为容易发现可能会有一个部门数量 $> \frac n 2$。

然后就到考验注意力的时候了。

我们注意到：如果部门 $1$ 的人数 $\ge \frac n 2$，那么部门 $2$ 与部门 $3$ 的人数总和肯定不超过 $\frac n 2$。

我需要让部门 $1$ 的人转到其他部门，那么就需要让损失的贡献尽可能小，即最大 $-$ 次大尽可能小。排序、贪心直到部门 $1$ 的人数恰好 $= \frac n 2$。而且这时候部门 $2$ 与 $3$ 的人数总是不会 $> \frac n 2$。

所以这样贪心是正确的。

相信很多人在考试的时候第一眼想 dp，我也为此浪费了 $20$ 分钟所以不要自责。

#include <bits/stdc++.h>
using namespace std;

struct node{
    int a, b, c;
};

void sol(){
    int n;
    cin>>n;
    vector<node> a(n + 5);
    vector<int> b(n + 5);
    for(int i = 1;i <= n;i++)
        cin>>a[i].a>>a[i].b>>a[i].c;
    long long res = 0;
    int cnt1 = 0, cnt2 = 0, cnt3 = 0;
    for(int i = 1;i <= n;i++){
        if(a[i].a >= max(a[i].b, a[i].c))
            b[i] = 1, res += a[i].a, cnt1++;
        else if(a[i].b >= max(a[i].a, a[i].c))
            b[i] = 2, res += a[i].b, cnt2++;
        else
            b[i] = 3, res += a[i].c, cnt3++;
    }
    vector<int> ans;
    for(int i = 1;i <= n;i++){
        if(cnt1 > n/2 && b[i] == 1)
            ans.push_back(a[i].a - max(a[i].b, a[i].c));
        else if(cnt2 > n/2 && b[i] == 2)
            ans.push_back(a[i].b - max(a[i].a, a[i].c));
        else if(cnt3 > n/2 && b[i] == 3)
            ans.push_back(a[i].c - max(a[i].a, a[i].b));
    }
    sort(ans.begin(), ans.end());
    int i = 0;
    while(cnt1 > n/2)
        res -= ans[i++], cnt1--;
    while(cnt2 > n/2)
        res -= ans[i++], cnt2--;
    while(cnt3 > n/2)
        res -= ans[i++], cnt3--;
    cout<<res<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
        sol();
}

反悔贪心

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		priority_queue<int,vector<int>,greater<int>>q[3];
		int n;scanf("%d",&n);int ans=0;
		for(int i=0;i<n;i++)
		{
			int mx=0,mn=30000,s=0,id=0;
			for(int j=0,x;j<3;j++)
			{
				scanf("%d",&x);
				if(x>=mx)mx=x,id=j;
				s+=x;mn=min(mn,x);
			}
			ans+=mx;q[id].push(mx*2+mn-s);
		}
		for(int i=0;i<3;i++)
			while(q[i].size()>n/2)
			{
				ans-=q[i].top();
				q[i].pop();
			}
		printf("%d\n",ans);
	}
	return 0;
}