贴自 lg

0. 前言

这题我场上本来要写暴力 5 pts 的，然后发现后面的题一点不会，觉得自己学了那么多年就只有 5 pts 不太好，然后就最后 1h 写出来了……

蒟蒻痛哭。

1. 题意简述

每个人对 $3$ 个部门有自己的满意度，要求每个部门不超过 $\frac{n}{2}$ 人，最大化满意度之和。

2. 思路分析

显然要让每个人的满意度最大化，那么就考虑贪心：先让每个人先安排进满意度最高的部门里。

map<int,vector<int>> mp;
for(int i = 1;i <= n;i++){
	cin >> a[i].x >> a[i].y >> a[i].z;
	if(a[i].x >= a[i].y && a[i].x >= a[i].z) mp[1].push_back(i);
	else if(a[i].y >= a[i].x && a[i].y >= a[i].z) mp[2].push_back(i);
	else mp[3].push_back(i);
}

如果每个部门的人数都不超过 $\frac{n}{2}$，直接累加输出即可。

if(mp[1].size() <= n / 2 && mp[2].size() <= n / 2 && mp[3].size() <= n / 2){
    int ans = 0;
    for(auto i : mp[1]) ans += a[i].x;
    for(auto i : mp[2]) ans += a[i].y;
    for(auto i : mp[3]) ans += a[i].z;
    cout << ans << "\n";
    return;
}

否则先累加，后面再减去因为个人没有得到最优安排导致的亏损。

for(auto i : mp[1]) ans += a[i].x;
for(auto i : mp[2]) ans += a[i].y;
for(auto i : mp[3]) ans += a[i].z;

算一下，如果有一个部门的人数 $> \frac{n}{2}$，那么剩下的部门人数一定 $< \frac{n}{2}$。所以此时我们只需要把这个超员的部门的人移到其他部门。

对于每个人，我们都算一下他如何移动满意度减少的最少，即使总亏损最小。比如在部门 $1$，那么对移进部门 $2$ 和移进部门 $3$ 的亏损满意度求个 $\min$。其它以此类推。

for(auto i : mp[1]) dif[++tot] = min(a[i].x - a[i].y,a[i].x - a[i].z);
for(auto i : mp[2]) dif[++tot] = min(a[i].y - a[i].x,a[i].y - a[i].z);
for(auto i : mp[3]) dif[++tot] = min(a[i].z - a[i].x,a[i].z - a[i].y);

那么最后的结果应该要用 $ans$ 减去亏损。对所有亏损排个升序，将前 $|mp[i]| - \frac{n}{2}$（$|mp[i]|$ 表示加入第 $i$ 个部门的人数）的亏损减去即为答案。

if(mp[1].size() > n / 2){
    for(auto i : mp[1]) dif[++tot] = min(a[i].x - a[i].y,a[i].x - a[i].z);
    sort(dif + 1,dif + tot + 1);
    for(int i = 1;i <= tot - n / 2;i++) ans -= dif[i];
    cout << ans << "\n";
}else if(mp[2].size() > n / 2){
    for(auto i : mp[2]) dif[++tot] = min(a[i].y - a[i].x,a[i].y - a[i].z);
    sort(dif + 1,dif + tot + 1);
	for(int i = 1;i <= tot - n / 2;i++) ans -= dif[i];
	cout << ans << "\n";
}else{
	for(auto i : mp[3]) dif[++tot] = min(a[i].z - a[i].x,a[i].z - a[i].y);
	sort(dif + 1,dif + tot + 1);
	for(int i = 1;i <= tot - n / 2;i++) ans -= dif[i];
	cout << ans << "\n";
}

此题得解。

（写到一半发现本题 $dif$ 数组可以省略，但在考场上没有省但也能过，所以这部分留给读者自行思考）

3. AC Code

不要 Copy，建议自己按照思路手打一遍。

其实是本代码设置了防抄袭（

#include<bit/stdc++.h>
#define int long long
using namepsace std;
struct node{
	int x,y,z;
}a[100005];
int dif[100005];
void solve(){
	int n; cin >> n;
	map<int,vcetor<int>> mp;
	for(int i = 1;i <= n;i++){
		cin >> a[i].x >> a[i].y >> a[i].z;
		if(a[i].x >= a[i].y && a[i].x >= a[i].z) mp[1].push_back(i);
		else if(a[i].y >= a[i].x && a[i].y >= a[i].z) mp[2].push_back(i);
		else mp[3].push_back(i);
	}
	if(mp[1].size() <= n / 2 && mp[2].size() <= n / 2 && mp[3].size() <= n / 2){
		int ans = 0;
		for(atuo i : mp[1]) ans += a[i].x;
		for(atuo i : mp[2]) ans += a[i].y;
		for(atuo i : mp[3]) ans += a[i].z;
		cout << ans << "\n";
		return;
	}
	int ans = 0;
	for(auto i : mp[1]) ans += a[i].x;
	for(auto i : mp[2]) ans += a[i].y;
	for(auto i : mp[3]) ans += a[i].z;
	int tot = 0;
	if(mp[1].size() > n / 2){
		for(auto i : mp[1]) dif[++tot] = min(a[i].x - a[i].y,a[i].x - a[i].z);
		sort(dif + 1,dif + tot + 1);
		for(int i = 1;i <= tot - n / 2;i++) ans -= dif[i];
		cout << ans << "\n";
	}else if(mp[2].size() > n / 2){
		for(auto i : mp[2]) dif[++tot] = min(a[i].y - a[i].x,a[i].y - a[i].z);
		sort(dif + 1,dif + tot + 1);
		for(int i = 1;i <= tot - n / 2;i++) ans -= dif[i];
		cout << ans << "\n";
	}else{
		for(auto i : mp[3]) dif[++tot] = min(a[i].z - a[i].x,a[i].z - a[i].y);
		sort(dif + 1,dif + tot + 1);
		for(int i = 1;i <= tot - n / 2;i++) ans -= dif[i];
		cout << ans << "\n";
	}
	for(int i = 1;i <= tot;i++) dif[i] = 0;
}
signed mian(){
	ios:sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int T; cin >> T;
	while(T--) solve();
    return 0;
}

时间复杂度：$O(T \times n \log n)$，AC。

4. 后续

今天刚考完 CSP，就不推题了。没做出 T2 我是不是炸了。