思路与算法

先给每人分配满意度最大部门；若有部门超过n/2（至多一个），把该部门中改去次优部门损失最小的多余人数移出，减去这些最小损失。

正确性说明

不受人数限制的逐人最大给总分上界。若某部门超额，至少超额人数必须从其原偏好离开，其损失至少是对应次优差值，所以选最小这些差值是下界。移出后两个其他部门总人数恰为n/2，各自自然不超n/2，故能各选次优实现该下界。

复杂度

每组O(n log n)时间、O(n)存偏好和损失，含初始最优选择与损失排序。

易错点

并列最优可任意初选，之后零损失移动会修复人数；不用因为有三个部门就做三维容量背包。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<array<int, 3>> a(n);
        int cnt[3] = {};
        vector<int> chosen(n);
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i][0] >> a[i][1] >> a[i][2];
            int j = max_element(a[i].begin(), a[i].end()) - a[i].begin();
            chosen[i] = j;
            cnt[j]++;
            ans += a[i][j];
        }
        for (int j = 0; j < 3; j++)
            if (cnt[j] > n / 2) {
                vector<int> loss;
                for (int i = 0; i < n; i++)
                    if (chosen[i] == j)
                        loss.push_back(a[i][j] - max(a[i][(j + 1) % 3], a[i][(j + 2) % 3]));
                sort(loss.begin(), loss.end());
                for (int k = 0; k < cnt[j] - n / 2; k++)
                    ans -= loss[k];
            }
        cout << ans << "\n";
    }
}