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

Iteration72 · 2025-11-01 21:36:37 · 题解

考场30min才写出来。
这里说一个很唐诗大模拟的思路，先输入 x_1,x_2,x_3 表示第 i 个人分别对 1,2,3 部门的满意度，再对 x_1,x_2,x_3 进行从大到小排序，用 p_i 表示排序后 x_i 在排序前的位置，并算排序后 x_1-x_2 和 x_2-x_3 作为对这 n 个人排序的关键字。

struct node{
    ll x[3],p[3],op,c;
}a[N];
inline bool cmp(node& x,node& y){
    return x.op>y.op||(x.op==y.op&&x.c>y.c);
}
inline bool cmp2(ll& x,ll& y){
    return x>y;
}

for(int ii=1;ii<=n;ii++){   //不要问我为什么是ii
    for(int i=0;i<=2;i++) cin>>a[ii].x[i],nx[i]=x[i];
    sort(a[ii].x,a[ii].x+3,cmp2);   //对x排序
    for(int i=0;i<=2;i++)
        for(int j=0;j<=2;j++)
            if(nx[j]==a[ii].x[i]) a[ii].p[i]=j;   //排序后在排序前序列的位置
    a[ii].op=a[ii].x[0]-a[ii].x[1];
    a[ii].c=a[ii].x[1]-a[ii].x[2];   //做差
}
sort(a+1,a+n+1,cmp);  //对每个人排序

然后从 1 到 n 对每个人进行具体的选择

for(int i=1;i<=n;i++){
    if(chosen[a[i].p[0]]<n/2){  //满意度最大的部门
        chosen[a[i].p[0]]++;
        ans+=a[i].x[0];
    }
    else if(chosen[a[i].p[1]]<n/2){   //第二的
        chosen[a[i].p[1]]++;
        ans+=a[i].x[1];
    }
    else{    //最差的
        chosen[a[i].p[2]]++;
        ans+=a[i].x[2];
    }
}cout<<ans<<endl;