club

時空 · 2025-11-01 21:10:26 · 题解

以此篇题解纪念我死去的 CSP 2025。

考场上被硬控 2h。玉玉了。

首先考虑暴力咋写。对于 n \le 200 的部分，考虑 f_{i,j,k} 表示前 i 个人，分了 j 个给社团 1，k 个给社团 2，那么分给社团 3 的就有 i-j-k 个人。转移可以做到 \mathcal{O(n^3)}。这个还是很容易的。

不会了咋办？看特殊性质！

性质 A 是简单的。考虑性质 B。此时社团 1,2 必然各选 n/2 个人。咋选呢？

不妨先考虑没限制的情况。这个时候每个人取满意度的最大值就好了。

考虑有限制的情况。假设没限制时社团 1,2 分别捞了 a,b 个人。不妨令 a \le b。发现当 b > n/2 时，我们需要将社团 2 的某些人分给社团 1。那么应该选取哪些呢？贪心地选取那些代价较小的即可。这里的代价就是每个人的最大值减去次大值。选取的过程可以用堆维护。

然后这个是可以推广到三个人的。那么做完了。

#include <bits/stdc++.h>

#define FstIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<ll, ll>

using namespace std;
using ll = long long;

const ll N = 3e5 + 2, M = 1e2 + 5; 
const ld eps = 1e-6;

ll T, n;
priority_queue <ll> p, q, k;

ll mymax(ll x, ll y, ll z) { return max(max(x, y), z); }

signed main()
{
    freopen("club.in", "r", stdin);
    freopen("club.out", "w", stdout);

    FstIO; 

    cin >> T; 
    while (T -- )
    {
        cin >> n;
        ll c1 = 0, c2 = 0, c3 = 0, s = 0; 
        for (ll i = 1; i <= n; ++ i )
        {
            ll x, y, z; cin >> x >> y >> z;
            if (mymax(x, y, z) == x) s += x, ++ c1, p.push(max(y - x, z - x));
            else if (mymax(x, y, z) == y) s += y, ++ c2, q.push(max(z - y, x - y));
            else s += z, ++ c3, k.push(max(x - z, y - z));
        }
        while (c1 > n / 2)
        {
            -- c1; 
            s += p.top(); p.pop();
        }
        while (c2 > n / 2)
        {
            -- c2; 
            s += q.top(); q.pop();
        }
        while (c3 > n / 2)
        {
            -- c3; 
            s += k.top(); k.pop();
        }
        cout << s << '\n';

        while (!p.empty()) p.pop();
        while (!q.empty()) q.pop();
        while (!k.empty()) k.pop();

    }    

    return 0;           
}