P14361 [CSP-S 2025] 社团招新 / club（官方数据）

· · 题解

怎么都用的反悔贪心……其实这题只需要一个简单的排序贪心。

思路

注意到：一个部门最多人数不超过 \frac n2。

所以，最多只会有一个部门达到限制。

易得，每个成员的最小值没有任何作用。

优先取最大值减次大值较小的成员，这样当最大值所在团队满员时切换到到次大值损耗较小。

当最大值减次大值相同时，优先取其中最大值较大成员。

如此保证绝对不劣。

综上所述，只需要排序一遍，将最大值减次大值作为第一关键字，最大值作为第二关键字从大到小排序即可。

丑陋的赛时代码

#include<bits/stdc++.h>
using namespace std;
int read(){
    int cnt = 0, sign = 1;
    char c = getchar();
    while(!isdigit(c)){
        if(c == '-')    sign = -1;
        c = getchar();
    }
    while(isdigit(c)){
        cnt = (cnt << 1) + (cnt << 3) + (c ^ 48);
        c = getchar();
    }
    return cnt * sign;
}//快读。
const int N = 1e5 + 10;
struct node{
    int a[5];
    int maxn, mid;
}mbr[N];//成员（member）。
int maxid(node x){
    if(x.a[1] >= x.a[2] && x.a[1] >= x.a[3])    return 1;
    if(x.a[2] >= x.a[1] && x.a[2] >= x.a[3])    return 2;
    return 3;
}//找最大值位置。
int midid(node x){
    if((x.a[1] <= x.a[2] && x.a[1] >= x.a[3]) || (x.a[1] <= x.a[3] && x.a[1] >= x.a[2]))    return 1;
    if((x.a[2] <= x.a[1] && x.a[2] >= x.a[3]) || (x.a[2] >= x.a[1] && x.a[2] <= x.a[3]))    return 2;
    return 3;
}//次大值位置。
bool cmp(node x, node y){
    return (x.a[x.maxn] - x.a[x.mid] == y.a[y.maxn] - y.a[y.mid]) ?  (x.a[x.maxn] > y.a[y.maxn]) : (x.a[x.maxn] - x.a[x.mid] > y.a[y.maxn] - y.a[y.mid]);
}//核心代码。
int main(){
//  freopen("club.in", "r", stdin);
//  freopen("club.out", "w", stdout);
    int T = read();
    while(T--){
        int cnt[5];
        memset(cnt, 0, sizeof(cnt));//记得初始化。
        int n = read();
        for(int i = 1; i <= n; i++){
            int a = read(), b = read(), c = read();
            mbr[i].a[1] = a;
            mbr[i].a[2] = b;
            mbr[i].a[3] = c;
            mbr[i].maxn = maxid(mbr[i]);
            mbr[i].mid = midid(mbr[i]);
        }
        sort(mbr + 1, mbr + n + 1, cmp);//排序。
        int ans = 0;
        for(int i = 1; i <= n; i++){
            if(cnt[mbr[i].maxn] == n / 2){
                ans += mbr[i].a[mbr[i].mid];
                cnt[mbr[i].mid]++;
            }else{
                ans += mbr[i].a[mbr[i].maxn];
                cnt[mbr[i].maxn]++;
            }//优先放进最大值所在桶，当前最大值所在桶满了之后取次大值。
        }
        printf("%d\n", ans);
    }
    return 0;
}

已通过官方数据。

蒟蒻赛时只写出 T1，T2正解写挂了，痛失 72 pts。

QwQ。