好好吃的反悔贪心

解析

首先不考虑每个人数限制，让所有人根据自己的喜好，选择满意度最高的部门，此时算得的满意度之和即为最理想的答案，接下来我们考虑如何调度人员，可以在损失满意度最少的情况下，满足各部门的人数限制。假设目前人数最多的部门中共有 x 人（显然，至多只有一个部门的人数会超过限制），我们改变其中 $(x-\frac{n}{2})$ 个人的意愿，将他们安排到其他部门。显然，这一操作也不会导致其他部门的人数过多。因而只需统计人数最多的部门中，所有人最大满意度与次大满意度之差（改变其部门的最小代价），找到部门中最小的 $(x-\frac{n}{2})$ 个人并将其换到第二喜欢的部门即可。

答案

#include <bits/stdc++.h>
#define ll long long
#define N 100100
using namespace std;

ll T, n, del[N];
struct Num
{
    ll a, b, c;
} num[N];

inline bool cmp(ll u, ll v) { return del[u] < del[v]; }
int main()
{
    cin >> T;
    while (T--)
    {
        ll ans = 0;
        vector<ll> A, B, C; // 表示各部门中包含哪些成员
        scanf("%lld", &n);
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld%lld%lld", &num[i].a, &num[i].b, &num[i].c);
            ll mx = max({num[i].a, num[i].b, num[i].c});
            // 计算最大值，并根据最大值选择其部门
            if (num[i].a == mx)
            {
                A.push_back(i);
                del[i] = mx - max(num[i].b, num[i].c);
            }
            else if (num[i].b == mx)
            {
                B.push_back(i);
                del[i] = mx - max(num[i].a, num[i].c);
            }
            else
            {
                C.push_back(i);
                del[i] = mx - max(num[i].a, num[i].b);
            }
            ans += mx;
        }
        if (A.size() > n / 2) // 第一个部门超标，找到最小的 x-n/2 人改变志愿
        {
            sort(A.begin(), A.end(), cmp);
            for (int i = 0; i < A.size() - n / 2; i++)
                ans -= del[A[i]];
        }
        if (B.size() > n / 2) // 第二个部门超标，找到最小的 x-n/2 人改变志愿
        {
            sort(B.begin(), B.end(), cmp);
            for (int i = 0; i < B.size() - n / 2; i++)
                ans -= del[B[i]];
        }
        if (C.size() > n / 2) // 第三个部门超标，找到最小的 x-n/2 人改变志愿
        {
            sort(C.begin(), C.end(), cmp);
            for (int i = 0; i < C.size() - n / 2; i++)
                ans -= del[C[i]];
        }
        printf("%lld\n", ans);
    }
}