P14361 [CSP-S 2025] 社團招新 / club 題解

題目鏈接

本人博客

前言

恩對，筆者在考場上思來想去，一共實現(xiàn)了 \(3\) 種代碼，但無一例外，均未調(diào)出來。怒得 \(25\) pts遺憾退場。

思路

首先需要讓每個人選自己最喜歡的社團（貪心），這無疑是最優(yōu)的。但是有可能不合法。

那我們考慮不合法應(yīng)該怎么辦。

設(shè) \(3\) 個部門人數(shù)為 \(a,b,c\)（其中 \(a \geq b \geq c\)）。如果不合法當(dāng)且僅當(dāng) \(a > \frac{n}{2}\) 且 \(b,c < \frac{n}{2}\)。證明如下。

| 由題意可知 \(a + b + c = n\)。若 \(a > \frac{n}{2}\)，則為 \(n-(b+c) > \frac{n}{2}\)，即 \(b+c < \frac{n}{2}\)。

因此只需要考慮其中一個部門不合法的情況。（筆者就是這個證明考場上腦子不好使，沒想到）

于是只需要預(yù)處理每個人從他最喜歡的部門到他次喜歡的部門的滿意度差。答案把多出來的人的差減去即可。

筆者這里用的是優(yōu)先隊列維護，時間復(fù)雜度 \(O(n \log n)\)。

代碼如下

#include<cstdio>
#include<iostream> 
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define int long long 
inline int Read(){
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-48;c=getchar();}
    return x*f;
}
inline void Write(int x){
    if(x<0){x=-x;putchar('-');}
    if(x>9) Write(x/10);
    putchar(x%10+'0');
}
const int N=1e5+10;
int T,n,ans;
int a[10]; 
priority_queue<int> q1,q2,q3;
//三個隊列用來維護每個部門的人數(shù)和每個人次大與最大之間的差
//注意默認為大根堆
int Max_3(int a,int b,int c){return max(max(a,b),c);}//最大值
void solve(){
    ans=0;
    while(!q1.empty()) q1.pop();
    while(!q2.empty()) q2.pop();
    while(!q3.empty()) q3.pop();
    //多測清空！
    n=Read();
    for(int i=1;i<=n;i++){//邊輸入邊處理
        for(int j=1;j<=3;j++){
            a[j]=Read();
        } 
        int t=Max_3(a[1],a[2],a[3]);
        if(a[1]==t){
            ans+=a[1];
            q1.push(max(a[2]-a[1],a[3]-a[1]));
            //因為默認大根堆，而我們最后貪心出隊的應(yīng)該是差最小的，所以可以存復(fù)數(shù)，出隊的時候直接加  
        }
        else if(a[2]==t){
            ans+=a[2];
            q2.push(max(a[1]-a[2],a[3]-a[2]));  
        }
        else if(a[3]==t){
            ans+=a[3];
            q3.push(max(a[1]-a[3],a[2]-a[3]));
        }
    }
    while(q1.size()>n/2){
        ans+=q1.top();q1.pop();
    }
    while(q2.size()>n/2){
        ans+=q2.top();q2.pop();
    }
    while(q3.size()>n/2){
        ans+=q3.top();q3.pop();
    }	
    printf("%lld\n",ans);
}
signed main(){
    T=Read();
    while(T--){
        solve();//多測函數(shù)好
    }
    return 0; 
}