初步无限制贪心若不考虑“每个部门人数不超过n2\frac{n}{2}2n”的限制最优策略是让每个人iii都进入其满意度最大的部门即选择max(ai,1,ai,2,ai,3)\max(a_{i,1}, a_{i,2}, a_{i,3})max(ai,1,ai,2,ai,3)。容量超标判断因为总人数为nnn限制为每个部门人数不超过n2\frac{n}{2}2n因此至多只有一个部门的人数会超过n2\frac{n}{2}2n。设贪心选择后三个部门的人数分别为c1,c2,c3c_1, c_2, c_3c1,c2,c3。如果c1,c2,c3≤n2c_1, c_2, c_3 \leq \frac{n}{2}c1,c2,c3≤2n则当前解即为最优解直接输出总和。如果某个部门不妨设为部门DDD的人数cDn2c_D \frac{n}{2}cD2n则必须将cD−n2c_D - \frac{n}{2}cD−2n个人调整到其他两个部门中。超标时的调整对于原本分配到部门DDD的每个人iii如果将其改派到另外两个部门中的某一个造成的满意度损失最小为Δiai,D−maxj≠Dai,j\Delta_i a_{i,D} - \max_{j \neq D} a_{i,j}Δiai,D−jDmaxai,j显然Δi≥0\Delta_i \geq 0Δi≥0。为了使总满意度最大化我们应当选择损失Δi\Delta_iΔi最小的人进行调整。我们将所有原先分配到部门DDD的人按照Δi\Delta_iΔi从小到大排序挑选损失最小的cD−n2c_D - \frac{n}{2}cD−2n个人移出部门DDD。是否会导致移入的部门人数超过n2\frac{n}{2}2n原先部门DDD的人数cD≤nc_D \leq ncD≤n。移出后部门DDD的人数恰好为n2\frac{n}{2}2n剩下的两个部门的总人数为n−n2n2n - \frac{n}{2} \frac{n}{2}n−2n2n。由于另外两个部门的人数非负且总和为n2\frac{n}{2}2n因此它们中的任何一个部门的人数都不可能超过n2\frac{n}{2}2n。因此只需将损失最小的cD−n2c_D - \frac{n}{2}cD−2n个人的损失减去即可无需担心二次超标问题。#includebits/stdc.husingnamespacestd;constintMAXN100005;// 用于存储各部门成员改选带来的最小损失intdiffs[3][MAXN],cnt[3];voidsolve(){intn;cinn;cnt[0]cnt[1]cnt[2]0;longlongtotal_sum0;for(inti0;in;i){inta[3];cina[0]a[1]a[2];// 选出最大值对应的部门intbest_dept0;if(a[1]a[best_dept])best_dept1;if(a[2]a[best_dept])best_dept2;total_suma[best_dept];// 找到除最优部门外的最大满意度intsecond_best-1;for(intj0;j3;j){if(jbest_dept)continue;if(second_best-1||a[j]second_best)second_besta[j];}// 存入对应部门的普通数组中diffs[best_dept][cnt[best_dept]]a[best_dept]-second_best;}intlimitn/2,over_dept-1;for(intj0;j3;j)if(cnt[j]limit){over_deptj;break;}// 若有部门超标按损失从小到大排序并减去超出的部分if(over_dept!-1){intneed_to_removecnt[over_dept]-limit;sort(diffs[over_dept],diffs[over_dept]cnt[over_dept]);for(inti0;ineed_to_remove;i)total_sum-diffs[over_dept][i];}couttotal_sum\n;}intmain(){intt;cint;while(t--){solve();}}
CSP-S 2025 T1社团招新
初步无限制贪心若不考虑“每个部门人数不超过n2\frac{n}{2}2n”的限制最优策略是让每个人iii都进入其满意度最大的部门即选择max(ai,1,ai,2,ai,3)\max(a_{i,1}, a_{i,2}, a_{i,3})max(ai,1,ai,2,ai,3)。容量超标判断因为总人数为nnn限制为每个部门人数不超过n2\frac{n}{2}2n因此至多只有一个部门的人数会超过n2\frac{n}{2}2n。设贪心选择后三个部门的人数分别为c1,c2,c3c_1, c_2, c_3c1,c2,c3。如果c1,c2,c3≤n2c_1, c_2, c_3 \leq \frac{n}{2}c1,c2,c3≤2n则当前解即为最优解直接输出总和。如果某个部门不妨设为部门DDD的人数cDn2c_D \frac{n}{2}cD2n则必须将cD−n2c_D - \frac{n}{2}cD−2n个人调整到其他两个部门中。超标时的调整对于原本分配到部门DDD的每个人iii如果将其改派到另外两个部门中的某一个造成的满意度损失最小为Δiai,D−maxj≠Dai,j\Delta_i a_{i,D} - \max_{j \neq D} a_{i,j}Δiai,D−jDmaxai,j显然Δi≥0\Delta_i \geq 0Δi≥0。为了使总满意度最大化我们应当选择损失Δi\Delta_iΔi最小的人进行调整。我们将所有原先分配到部门DDD的人按照Δi\Delta_iΔi从小到大排序挑选损失最小的cD−n2c_D - \frac{n}{2}cD−2n个人移出部门DDD。是否会导致移入的部门人数超过n2\frac{n}{2}2n原先部门DDD的人数cD≤nc_D \leq ncD≤n。移出后部门DDD的人数恰好为n2\frac{n}{2}2n剩下的两个部门的总人数为n−n2n2n - \frac{n}{2} \frac{n}{2}n−2n2n。由于另外两个部门的人数非负且总和为n2\frac{n}{2}2n因此它们中的任何一个部门的人数都不可能超过n2\frac{n}{2}2n。因此只需将损失最小的cD−n2c_D - \frac{n}{2}cD−2n个人的损失减去即可无需担心二次超标问题。#includebits/stdc.husingnamespacestd;constintMAXN100005;// 用于存储各部门成员改选带来的最小损失intdiffs[3][MAXN],cnt[3];voidsolve(){intn;cinn;cnt[0]cnt[1]cnt[2]0;longlongtotal_sum0;for(inti0;in;i){inta[3];cina[0]a[1]a[2];// 选出最大值对应的部门intbest_dept0;if(a[1]a[best_dept])best_dept1;if(a[2]a[best_dept])best_dept2;total_suma[best_dept];// 找到除最优部门外的最大满意度intsecond_best-1;for(intj0;j3;j){if(jbest_dept)continue;if(second_best-1||a[j]second_best)second_besta[j];}// 存入对应部门的普通数组中diffs[best_dept][cnt[best_dept]]a[best_dept]-second_best;}intlimitn/2,over_dept-1;for(intj0;j3;j)if(cnt[j]limit){over_deptj;break;}// 若有部门超标按损失从小到大排序并减去超出的部分if(over_dept!-1){intneed_to_removecnt[over_dept]-limit;sort(diffs[over_dept],diffs[over_dept]cnt[over_dept]);for(inti0;ineed_to_remove;i)total_sum-diffs[over_dept][i];}couttotal_sum\n;}intmain(){intt;cint;while(t--){solve();}}
