题解：P14361 [CSP-S 2025] 社团招新 / club（民间数据）

· · 题解

思路

注意到：当最大的一个分组达到了 \dfrac{n}{2} 人时，另外第二大的分组一定不大于 \dfrac{n}{2} 人。 因此只需要保证最大的一个分组合法即可。

先假设所有人都分配到了各自最喜欢的组，将这一种分配方式设为理想状态。但是，理想状态大多是不合法的状态，因此我们需要找到与理想状态相差最小的最优解。

对于每一个人都有最喜欢的组别和第二喜欢的组别。为了满足最大的分组人数不大于 \dfrac{n}{2} 人，就应当把一部分人从最喜欢的组别调整到第二喜欢的组别。将一个人的损失定义为最大的满意度减去第二大的满意度。我们只需要将损失较小的人调走就可以满足总体损失较小，进而推导出最优解。

代码

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e5 + 5;
int T, n, ans, cnt[5];
pair<int, int> d[5];

// name 表示组名
// sat  表示满意度
// loss 表示调走一个人的损失
struct People {
    int name1, sat1, name2, sat2, loss;
} p[N];

bool cmp(People A, People B) { return A.loss > B.loss; }

signed main() {
    cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--) {
        ans = 0;
        memset(cnt, 0, sizeof cnt);
        cin >> n;
        for (int i = 1; i <= n; i++) {  // 计算最喜欢的组和第二喜欢的组
            cin >> d[1].first >> d[2].first >> d[3].first;
            d[1].second = 1, d[2].second = 2, d[3].second = 3;
            sort(d + 1, d + 4, greater<pair<int, int>>());
            p[i].name1 = d[1].second, p[i].sat1 = d[1].first;
            p[i].name2 = d[2].second, p[i].sat2 = d[2].first;
            p[i].loss = p[i].sat1 - p[i].sat2;
        }
        sort(p + 1, p + 1 + n, cmp);    // 按照损失大小排名
        for (int i = 1; i <= n; i++) {  // 贪心
            if (cnt[p[i].name1] >= n / 2)
                cnt[p[i].name2]++, ans += p[i].sat2;
            else
                cnt[p[i].name1]++, ans += p[i].sat1;
        }
        cout << ans << "\n";
    }
    return 0;
}