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

· · 题解

首先，一个最粗略的贪心是每行取一个最大的数，但题目还有一个条件是每个部门不超过 \frac{n}{2} 个人，那么，如果在选的过程中某个部门要选的人多出来了，那么之前选这个部门的人（包括现在选的这个人）多出来的人就要选其他部门。所以，我们要维护每一行的次大数，当部门满员时，在目前所有选这个部门的人中选一个最大数与次大数之差最小的一个人，让他选其它部门，即用次大数替换最大数，这样损失最小。这个过程可以用一个优先队列来维护。

:::info[参考代码]

//Author: mairuisheng
//#pragma GCC optimize(3)
#include<cstdio>
#include<queue>
#define int long long
using namespace std;
inline int read()
{
    int x=0,f=1;
    char s;
    s=getchar();
    while(s<48||s>57)
    {
        if(s=='-')f=-f;
        s=getchar();
    }
    while(s>47&&s<58)
    {
        x=(x<<3)+(x<<1)+s-48;
        s=getchar();
    }
    return x*f;
}
constexpr int N=1e5+1;
priority_queue<int,vector<int>,greater<int> > q,q2,q3;
int a[N][4];
int n,lmt;
void Solve()
{
    while(!q.empty())q.pop();
    while(!q2.empty())q2.pop();
    while(!q3.empty())q3.pop();
    int cnt[3];
    cnt[0]=cnt[1]=cnt[2]=0;
    n=read();
    lmt=n>>1ll;
    int i,ans=0;
    for(i=1;i<=n;++i)
    {
        a[i][0]=read();
        a[i][1]=read();
        a[i][2]=read();
        a[i][3]=max(a[i][0],max(a[i][1],a[i][2]));
        a[i][3]=a[i][0]+a[i][1]+a[i][2]-a[i][3]-min(a[i][0],min(a[i][1],a[i][2]));
    }
    for(i=1;i<=n;++i)
    {
        if(a[i][0]>=a[i][1]&&a[i][0]>=a[i][2])
        {
            q.push(a[i][0]-a[i][3]);
            ans+=a[i][0];
            if(cnt[0]==lmt)
            {
                ans-=q.top();
                q.pop();
            }
            else ++cnt[0];
        }
        else if(a[i][1]>=a[i][0]&&a[i][1]>=a[i][2])
        {
            q2.push(a[i][1]-a[i][3]);
            ans+=a[i][1];
            if(cnt[1]==lmt)
            {
                ans-=q2.top();
                q2.pop();
            }
            else ++cnt[1];
        }
        else
        {
            q3.push(a[i][2]-a[i][3]);
            ans+=a[i][2];
            if(cnt[2]==lmt)
            {
                ans-=q3.top();
                q3.pop();
            }
            else ++cnt[2];
        }
    }
    printf("%lld\n",ans);
}
signed main()
{
    int T;
    T=read();
    while(T--)Solve();
    return 0;
}

:::