P14361 [CSP-S 2025] 社团招新 / club 题解

题目大意

将

n

个新成员分配到 3 个部门，每个成员对每个部门有不同的满意度

a_{i,j}

。要求：

每个部门人数不超过 $\frac{n}{2}$
最大化总满意度

算法思路

核心思想：反悔贪心

这道题的关键在于先贪心分配，再调整优化。

算法流程

第一步：贪心初始分配

对每个成员，直接分配到满意度最高的部门：

CPP

for (int i = 0; i < n; i++) {
    int best = 0;
    if (a[i][1] > a[i][best]) best = 1;
    if (a[i][2] > a[i][best]) best = 2;

    assign[i] = best;
    ans += a[i][best];
    cnt[best]++;
}

此时可能某些部门人数超过

\frac{n}{2}

，需要调整。

第二步：反悔调整

策略：对于人数超过限制的部门，找到转移损失最小的成员，调整到其他部门。

关键问题：如何快速找到转移损失最小的成员？

解决方案：使用**优先队列（小根堆）**维护每个部门的成员，按照转移到其他部门的最小损失排序。

CPP

// 对每个部门维护一个优先队列
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq[3];

// 初始化时计算每个人的转移损失
for (int i = 0; i < n; i++) {
    // ... 分配到best部门 ...

    // 计算从best转移到其他部门的最小损失
    int minLoss = INT_MAX;
    for (int j = 0; j < 3; j++) {
        if (j != best) {
            minLoss = min(minLoss, a[i][best] - a[i][j]);
        }
    }
    pq[best].push({minLoss, i});
}

第三步：执行调整

当某个部门人数超限时：

找到人数最多的部门 maxDept
从该部门的优先队列取出转移损失最小的成员
将该成员转移到未满的部门
更新答案和计数器

CPP

while (cnt[0] > limit || cnt[1] > limit || cnt[2] > limit) {
    // 找到人数最多的部门
    int maxDept = ...;

    // 取出转移损失最小的成员
    auto [loss, idx] = pq[maxDept].top();
    pq[maxDept].pop();

    // 检查该成员是否还在原部门（延迟删除）
    if (assign[idx] != maxDept) continue;

    // 找到可转移的目标部门
    int target = 找到未满的部门且转移损失最小;

    // 执行转移
    ans -= realLoss;
    cnt[maxDept]--;
    assign[idx] = target;
    cnt[target]++;

    // 更新优先队列
    pq[target].push({新的转移损失, idx});
}

正确性证明

为什么贪心是正确的？

初始分配最优性：每个人选择自己最满意的部门，获得局部最优解
调整最小化损失：当需要调整时，我们选择损失最小的调整方案
全局最优性：由于每次调整都是最优的，最终结果接近全局最优

关键观察

如果初始分配满足约束，则已经是最优解
如果不满足约束，调整时选择损失最小的成员移动，保证总损失最小
每个成员最多被调整常数次，复杂度可控

复杂度分析

时间复杂度

初始分配： $O(n)$
建堆： $O(n \log n)$
调整阶段：每个成员最多进出队列 $O(1)$ 次，每次操作 $O(\log n)$
总复杂度： $O(n \log n)$

空间复杂度

三个优先队列： $O(n)$
辅助数组： $O(n)$
总复杂度： $O(n)$

优化技巧

1. 延迟删除

优先队列不支持高效删除指定元素。使用 assign[idx] 记录当前分配，取出元素时检查是否还在原部门。

CPP

if (assign[idx] != maxDept) continue; // 已经被调整过

2. 优先队列维护

每个部门维护一个小根堆，存储 {转移损失, 成员编号}，快速找到最小损失。

3. 实时更新

成员被调整到新部门后，重新计算转移损失并加入新部门的优先队列。

代码实现

CPP

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fclose fclose(stdin), fclose(stdout)
#define debug(x) cerr << #x << " = " << (x) << endl

void solve() {
    int n;
    cin >> n;

    vector<array<int, 3>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }

    int limit = n / 2;

    // 先给每个人分配最优部门（贪心）
    long long ans = 0;
    vector<int> assign(n);

    // 用优先队列维护每个部门中的人，按照转移损失排序
    // pq[i] 存储分配到部门i的人，按照转移到其他部门的最小损失排序（小根堆）
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq[3];

    vector<int> cnt(3, 0);

    for (int i = 0; i < n; i++) {
        // 选择满意度最大的部门
        int best = 0;
        if (a[i][1] > a[i][best]) best = 1;
        if (a[i][2] > a[i][best]) best = 2;

        assign[i] = best;
        ans += a[i][best];
        cnt[best]++;

        // 计算从best转移到其他部门的最小损失
        int minLoss = INT_MAX;
        for (int j = 0; j < 3; j++) {
            if (j != best) {
                minLoss = min(minLoss, a[i][best] - a[i][j]);
            }
        }
        pq[best].push({minLoss, i});
    }

    // 调整：如果有部门超过limit，需要把人调走
    while (cnt[0] > limit || cnt[1] > limit || cnt[2] > limit) {
        // 找到人数最多的部门
        int maxDept = 0;
        for (int i = 1; i < 3; i++) {
            if (cnt[i] > cnt[maxDept]) maxDept = i;
        }

        if (cnt[maxDept] <= limit) break;

        // 从优先队列中取出转移损失最小的人
        while (!pq[maxDept].empty()) {
            auto [loss, idx] = pq[maxDept].top();
            pq[maxDept].pop();

            // 检查这个人是否还在maxDept（可能已经被调整过了）
            if (assign[idx] != maxDept) continue;

            // 找到可以转移的目标部门
            int target = -1;
            int realLoss = INT_MAX;
            for (int j = 0; j < 3; j++) {
                if (j != maxDept && cnt[j] < limit) {
                    int curLoss = a[idx][maxDept] - a[idx][j];
                    if (curLoss < realLoss) {
                        realLoss = curLoss;
                        target = j;
                    }
                }
            }

            if (target == -1) continue;

            // 执行调整
            ans -= realLoss;
            cnt[maxDept]--;
            assign[idx] = target;
            cnt[target]++;

            // 重新计算并加入优先队列
            int newMinLoss = INT_MAX;
            for (int j = 0; j < 3; j++) {
                if (j != target) {
                    newMinLoss = min(newMinLoss, a[idx][target] - a[idx][j]);
                }
            }
            pq[target].push({newMinLoss, idx});
            break;
        }
    }

    cout << ans << endl;
}

signed main() {
    //file(club);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    //fclose;
    return 0;
}

样例分析

样例 1-1

输入：

CPP

初始贪心分配：

成员 1：最大 4（部门 1）
成员 2：最大 4（部门 3）
成员 3：最大 5（部门 1）
成员 4：最大 5（部门 2）

部门人数：[2, 1, 1]，满足约束，答案 = 4+4+5+5 = 18

样例 1-2

输入：

CPP