社团招新

解题思路分析

如果没有任何约束（每个部门人数不限制），显然每个人都应该选择自己满意度最大的那个部门，即 $d_i = \arg\max_{j \in \{1,2,3\}} \{a_{i,j}\}$。

但有了“每个部门人数不超过 $\frac{n}{2}$”的限制后：

是否存在多个部门人数超过 $\frac{n}{2}$？

因为三个部门人数之后固定为 $n$，若有两个部门人数均超半，总人数必超 $n$ 产生矛盾。因此，最多只有一个部门人数会超过 $\frac{n}{2}$。

分类讨论与贪心策略：

• 情况 1：贪心选择后，没有任何部门人数超过 $\frac{n}{2}$

  直接输出所有人选最大满意度之和即可。

• 情况 2：贪心选择后，恰好有一个部门（假设为部门 $K$）人数达到了 $C > \frac{n}{2}$

  若部门 $K$ 选入人数 $C$ 超过上限 $\frac{n}{2}$，需挑选 $C - \frac{n}{2}$ 人改派至其他部门：

  改派成员 $i$ 的最小满意度损失为：

  $\Delta_i = a_{i,K} - \max_{j \neq K} \{a_{i,j}\}$

  具体调整策略：

  • 贪心选择 $\Delta_i$ 最小 的 $C - \frac{n}{2}$ 个人进行调离。
  • 用初始满意度总和减去这部分人的最小损失和，即得满足限制的最高满意度。

算法步骤

1. 初始贪心分配

   • 遍历每个人 $i$，找出他满意度最大的部门 $opt_i = \arg\max_{j \in \{1,2,3\}} a_{i,j}$。
   • 累加基础总满意度 ans += a[i][opt_i]。
   • 统计每个部门被选中的人数 cnt[opt_i]++。

2. 检查并调整

   • 寻找是否存在某个部门 $K$ 满足 cnt[K] > n / 2。

   • 如果不存在，直接输出 ans。

   • 如果存在部门 $K$：

     • 收集所有被初始分配到部门 $K$ 的成员 $i$ 的损失值：

       $\text{cost}_i = a_{i,K} - \max_{j \neq K} \{a_{i,j}\}$

     • 将这些损失值从小到大排序。

     • 取前 cnt[K] - n / 2 个最小损失值并累加，从 ans 中扣除。

3. 输出结果

   输出最终的 ans。

参考代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    long long sum_ans = 0;
    vector<int> cnt(4, 0); // 统计每个部门的人数（1, 2, 3）
    vector<vector<long long>> chosen(4); // 记录分配到各个部门的人员调离损失

    for (int i = 0; i < n; ++i) {
        long long a1, a2, a3;
        cin >> a1 >> a2 >> a3;

        // 找出该成员的最大满意度及对应部门
        int opt = 1;
        long long max_a = a1;

        if (a2 > max_a) {
            max_a = a2;
            opt = 2;
        }
        if (a3 > max_a) {
            max_a = a3;
            opt = 3;
        }

        sum_ans += max_a;
        cnt[opt]++;

        // 计算调离该部门的最小损失：max_a - 次大值
        long long sec_a = 0;
        if (opt == 1) sec_a = max(a2, a3);
        else if (opt == 2) sec_a = max(a1, a3);
        else sec_a = max(a1, a2);

        chosen[opt].push_back(max_a - sec_a);
    }

    // 检查是否有部门超限
    int limit = n / 2;
    int over_dept = 0;

    for (int k = 1; k <= 3; ++k) {
        if (cnt[k] > limit) {
            over_dept = k;
            break;
        }
    }

    // 如果有部门超额，进行贪心调整
    if (over_dept != 0) {
        int need_remove = cnt[over_dept] - limit;
        auto& costs = chosen[over_dept];

        // 按损失从弱到强（从小到大）排序
        sort(costs.begin(), costs.end());

        // 减去损失最小的几个调整成本
        for (int i = 0; i < need_remove; ++i) {
            sum_ans -= costs[i];
        }
    }

    cout << sum_ans << "\n";
}

int main() {
    // 加速 I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

代码细节

1. 类型选择： 满意度总和最高可达 $10^5 \times (2 \times 10^4) = 2 \times 10^9$，虽然略低于标准的 32 位 signed int 上限，但为了防止累加溢出，统一使用 long long 存储满意度总和与损失值。
2. 损失计算： 变量 chosen[opt] 记录所有被分配到 opt 部门的人如果改去其他两个部门中的最大满意度部门所带来的满意度损失。
3. 极速 I/O： 使用 ios_base::sync_with_stdio(false); cin.tie(NULL); 确保处理多组数据（$t \le 5$, $n \le 10^5$）时能在 $1.00\text{s}$ 内快速完成读写。

复杂度分析

• 时间复杂度： 每个人寻找最大值耗时 $O(1)$，收集损失值耗时 $O(n)$，对损失值数组排序耗时 $O(n \log n)$。单组测试数据时间复杂度为 $O(n \log n)$。对于 $n \le 10^5$ 和 $t \le 5$，总计算量完全可以通过 $1.00\text{s}$ 的限制。
• 空间复杂度： 需要存储输入和临时损失值数组，空间复杂度为 $O(n)$，符合 $512\text{MB}$ 限制。