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

Terminal_P · 2025-11-01 21:03:52 · 题解

题目描述略。

通过了民间数据。

不明白这题为什么会想到神秘反悔。

考虑贪心。下文把第 i 个人在某个部门的收益分别记作 A_i, B_i, C_i。

由于方案合法当且仅当所有部门人数不超过 \dfrac{n}{2}，显然最多有一个部门的人数不合法。

不考虑人数限制，计算收益最大值是简单的。

如果有一个部门（钦定为 A ）人数过多，考虑将其转移到另外两个部门中的一个。对于每个 A 中的人，将其转移出 A 的收益减小值是 \min\{A_i - B_i, A_i - C_i\}。

将 A 中的人关于 \min\{A_i - B_i, A_i - C_i\} 升序排序，取前 |A| - \dfrac{n}{2} 个处理即可。

时间复杂度 O(n \log n)，瓶颈在排序。空间复杂度 O(n)。可以通过此题。

:::success[代码]

void solve(i32 _) {
  i32 n;
  i64 ans = 0;
  std::cin >> n;
  std::vector<std::vector<i32>> a(4, std::vector<i32>(n + 2, 0));
  std::vector<std::vector<i32>> g(4);
  for (i32 i = 1; i <= n; i++)
    for (i32 j = 1; j <= 3; j++) std::cin >> a[j][i];
  for (i32 i = 1; i <= n; i++) {
    auto [x, y, z] = (std::tuple<i32, i32, i32>){a[1][i], a[2][i], a[3][i]};
    i32 mx = std::max(x, std::max(y, z));
    ans += mx;
    if (mx == x)
      g[1].push_back(std::min(x - y, x - z));
    else if (mx == y)
      g[2].push_back(std::min(y - x, y - z));
    else
      g[3].push_back(std::min(z - x, z - y));
  }
  for (i32 i = 1; i <= 3; i++) {
    auto &b = g[i];
    std::sort(b.begin(), b.end());
    for (i32 i = 0; i < (i32)b.size() - n / 2; i++) ans -= b[i];
  }
  std::cout << ans << endl;
  return void();
}

:::