P14361 [CSP-S 2025] 社團招新 / club
當時考試的時候五十分鐘寫完的，不像個綠題，降黃還差不多。
雖然說反悔貪心的板子是綠，但是我考試想這個思路的時候，沒有意識到這是個反悔貪心。
我是怎么想的呢？假設你就是人類小 L，你作為人類會怎么分？肯定是先讓大家選最滿意的社團了。如果此時哪個社團都沒有超人數，那么直接輸出答案就好了。
（以下稱這部分的答案是 \(sum\)，即 \(n\) 個人最大滿意度之和）
如果有超人數的社團呢？首先，任意時刻都至多只有一個社團會超人數（否則人數超過 \(n\)），其次，我們還是用人類的視角去看這個問題。
（以下將三個社團編號為 \(0,1,2\)，假設當前超了人數的社團編號為 \(id\)，報名它的人數為 \(num_{id}\)）
正常情況下超了人數，會長出面協調的時候，肯定會盡可能小地調動人，而且只會調整報了 \(id\) 社團的人，讓他們去另外的社團。
我們可以把這個過程看作調人后，\(sum\) 不斷減當前這個人 最滿意社團滿意度 與 當前社團滿意度 的差值。
那我們為了收益最大，\(sum\) 減的值最小，一來一定會把他們調整到第二滿意的社團，二來我們會不斷選擇 當前報了 \(id\) 社團 且 最滿意社團滿意度 與 第二滿意社團滿意度 差值最小 的人，這樣能保證 \(sum\) 減的數字盡可能小。
這就是我們以人類視角想出來的正解。那有的人就要問了：我這樣調整社團的時候，沒有保證其他兩個社團不超人數限制。萬一我調整完 \(id\) 社團后，又有一個社團人數超限了呢？
事實上并不會出現這種情況。因為我剛才的過程調整了盡可能少的人，也就是調整完后恰有 \(num_{id}=n/2\)。如果說此時有另一個社團人數超限，那么總人數就會大于 \(n\)，矛盾。故我們執行此貪心策略時不用擔心其他社團人數超限的問題。
代碼：
P14361
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<48){
if(c=='-') f=-1;
c=getchar();
}
while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
const int N=1e5+5;
int T,n,a[3][N],cha[3][2][N],sum,num[3],cho[N];
//cha[id][0/1][i]:0/1分別表示第i個人對id社團的滿意度與另兩個社團的滿意度之差
//比如cha[1][0][i]表示第i個人對第1個社團的滿意度與對第0個社團的滿意度之差
//cha[1][1][i]表示 第i個人對第1個社團的滿意度與對第2個社團的滿意度之差
//num[id]、sum:同題解
//cho[i]:i調整前選了哪個社團
priority_queue<int,vector<int>,greater<int> > q;
//q是小根堆，用來處理當前最小的 最滿意社團 與 次滿意社團 滿意度之差
inline void INIT(){
num[0]=num[1]=num[2]=0;sum=0;
for(int i=1;i<=n;i++){
cha[0][0][i]=cha[0][1][i]=cha[1][0][i]=0;
cha[1][1][i]=cha[2][0][i]=cha[2][1][i]=0;
cho[i]=-1;
}
while(!q.empty()) q.pop();
}
inline void cl(int id){//處理編號為id的人
if(a[0][id]>=a[1][id]&&a[0][id]>=a[2][id]){//選擇0社團
num[0]++;cho[id]=0;
}
else if(a[1][id]>=a[0][id]&&a[1][id]>=a[2][id]){//選擇1社團
num[1]++;cho[id]=1;
}
else if(a[2][id]>=a[0][id]&&a[2][id]>=a[1][id]){//選擇2社團
num[2]++;cho[id]=2;
}
cha[0][0][id]=a[0][id]-a[1][id];cha[0][1][id]=a[0][id]-a[2][id];
cha[1][0][id]=a[1][id]-a[0][id];cha[1][1][id]=a[1][id]-a[2][id];
cha[2][0][id]=a[2][id]-a[0][id];cha[2][1][id]=a[2][id]-a[1][id];
}
inline void solve(int id){
//solve(id):當前編號為id的社團人數超了，我們該怎么處理
int numb=0;
for(int i=1;i<=n;i++){
if(cho[i]==id){
q.push(min(cha[id][0][i],cha[id][1][i]));
numb++;
}
}
while(numb>n/2){
int s=q.top();q.pop();
sum-=s;
numb--;
}
}
signed main(){
T=read();
while(T--){
n=read();
INIT();//多測不清空，親人兩行淚
//sum同題解
for(int i=1;i<=n;i++){
a[0][i]=read(),a[1][i]=read(),a[2][i]=read();
sum+=max(max(a[0][i],a[1][i]),a[2][i]);
cl(i);
}
if(num[0]>n/2){
solve(0);
}
else if(num[1]>n/2){
solve(1);
}
else if(num[2]>n/2){
solve(2);
}
printf("%lld\n",sum);
}
return 0;
}
浙公網安備 33010602011771號