S组第一题

AA12_G · 2025-11-27 19:59:52 · 个人记录

思路

首先如果没那个不能超过一半的限制，肯定每个人都选那个最优的。

如果加上了那个限制呢？那么有可能会出现有个社团过于火爆。

如何去应对这个情况呢？

不知道大家有没有知道清华那边有个叫“调济”的模式，就是给那个分低的从人超了的专业挪到比较冷清的专业。

我们这里也要用类似于这个模式的思维。将超了的一些人都给他调到那个比较冷清的社团。

但是我们这里的第一关键字，不是分数。

那是什么呢？我们知道如果一个人去调专业的话，他对答案的贡献就会减少一个（之前的社团喜欢度-调到的社团的喜欢度）。举个例子，如果这个人之前的社团是 1，要给调到 2 这个社团，那么对答案的贡献就会减少 a_{i,1} - a_{i,2}。

为了最优，我们给他调到的社团一定是他第二喜欢的（因为第一次选的那个应该是最喜欢的）。

其次，调完之后会不会出现超的情况呢？显然不会。因为最火爆的那个社团应该剩下 \frac{n}{2} 个人，那么剩下的人无论怎么放都不会超。

于是我们考虑预处理一个每个人（第一的社团喜欢度-第二的社团的喜欢度），到时候在超的那里面以这个为关键字进行一个排序，找到那些对答案影响最小的，只能委屈一下他们啦。

于是就可以写代码了。

#include <bits/stdc++.h>
using namespace std;
int n, a[114514][5], to[114514], to_a[114514], to_b[114514], to_c[114514];
bool cmp (int a, int b)
{
    return to[a] > to[b];
}
void mian()
{

    int cnta = 0, cntb = 0, cntc = 0, maxx = 0;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i ++) 
    {
        cin >> a[i][1] >> a[i][2] >> a[i][3];
        int maxx = max (a[i][1], max (a[i][2], a[i][3]));
        int cmax = a[i][1] + a[i][2] + a[i][3] - maxx - min (min (a[i][1], a[i][2]), a[i][3]);
        if (maxx == a[i][1]) to_a[++cnta] = i;
        else if (maxx == a[i][2]) to_b[++cntb] = i;
        else to_c[++cntc] = i;
        to[i] = cmax - maxx;
        ans += maxx;
    }
    sort (to_a + 1, to_a + cnta + 1, cmp);
    sort (to_b + 1, to_b + cntb + 1, cmp);
    sort (to_c + 1, to_c + cntc + 1, cmp);
    if (cnta > n / 2)
    {
        for (int i = 1; i <= cnta - n / 2; i ++) ans += to[to_a[i]];
    }
    else if (cntb > n / 2)
    {
        for (int i = 1; i <= cntb - n / 2; i ++) ans += to[to_b[i]];
    }
    else if (cntc > n / 2)
    {
        for (int i = 1; i <= cntc - n / 2; i ++) ans += to[to_c[i]];
    }
    cout << ans << endl;
}
int main()
{
    int T;
    cin >> T;
    while (T --) mian();
}