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

Hughpig · 2025-11-01 20:40:17 · 题解

直接按每个成员满意度最大值分类分部门，扔进 vector 里。因为只有其大小超过 \dfrac{n}{2} 才会导致不合法，所以最多只有一个部门大小超了。

对于大小超了的部门，要选某些元素换个部门，选到满意度次高的部门是最优的。显然最多只有一个部门大小超过 \dfrac{n}{2}，所以换部门这件事不会导致某个部门大小超限。

记超限的部门大小为 s，把超限的部门中的某个元素换个部门，会让答案减小其最大满意值与次大满意值的差。

我们要让答案最大化，也就是让要减小的满意值越小越好，所以挑选这个差值尽量小的成员让他们换部门。

按这个从大到小排序选最小的后让 \lceil \dfrac{n}{2}\rceil\sim s 这些成员换部门就能做到最优。