题目链接 题意解读 有n个人，每个人要去3个部门中的一个，但是每一个部门最多容纳n/2个人。每个人到各个部门有一定美好值，求最大美好值总和 思路 对于每一个人，求这个人去每一个部门的最大美好值和次大美好值。 Q1 为什么要求最大美好值和次大美好值？ A1 如果某一个部门爆满了，就找一个合适的部门让该部门的人转移过去，并保证损失最小 Q2 该存最小损失呢，怎么办呢 A2 想想有什么办法可以一直往里面放东西还一直返回最小的？优先队列成为首选 Q3 现在知道怎么存，怎么求呢？ A3 就用每一个人去各个部门的最大美好值-次大美好值 代码参考 总结 这道题用贪心的策略，用优先队列维护。 教会我们：从最大总和的组成来考虑，比如这道题是最大美丽值总和=所有人都选最大美丽值部门的美丽值和-部门饱满后得要踢走的人里美丽值损失最小。依旧长难句 警钟敲烂 空间记得开够！

反悔贪心 这个>n/2的条件看起来很唐（也就是说最多只有一个组别人会多）从这里入手 一开时都放到最想去的 然后 把踢到其他组里面代价（也就是这个人第一想去和第二想去的差值）最小的人牺牲给到其他组 sum减去代价即可 时间复杂度：TNlogN 我是蒟蒻想了这么久原谅我 求赞

左转去洛谷，全站公开的题解必须康康点个赞。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 0. 前言 首先希望 2025 CSP rp++！ 这题我场上本来要写暴力 5 pts 的，然后发现后面的题一点不会，觉得自己学了那么多年就只有 5 pts 不太好，然后就最后 1h 写出来了…… 蒟蒻痛哭。 1. 题意简述 每个人对 333 个部门有自己的满意度，要求每个部门不超过 n2\frac{n}{2}2n 人，最大化满意度之和。 2. 思路分析 显然要让每个人的满意度最大化，那么就考虑贪心：先让每个人先安排进满意度最高的部门里。 如果每个部门的人数都不超过 n2\frac{n}{2}2n ，直接累加输出即可。 否则先累加，后面再减去因为个人没有得到最优安排导致的亏损。 算一下，如果有一个部门的人数 $ > \frac{n}{2}$，那么剩下的部门人数一定 <n2< \frac{n}{2}<2n 。所以此时我们只需要把这个超员的部门的人移到其他部门。 对于每个人，我们都算一下他如何移动满意度减少的最少，即使总亏损最小。比如在部门 111，那么对移进部门 222 和移进部门 333 的亏损满意度求个 min⁡\minmin。其它以此类推。 那么最后的结果应该要用 ansansans 减去亏损。对所有亏损排个升序，将前 ∣mp[i]∣−n2|mp[i]| - \frac{n}{2}∣mp[i]∣−2n （∣mp[i]∣|mp[i]|∣mp[i]∣ 表示加入第 iii 个部门的人数）的亏损减去即为答案。 此题得解。 （写到一半发现本题 difdifdif 数组可以省略，但在考场上没有省但也能过，所以这部分留给读者自行思考） 3. AC CODE 不要 Copy，建议自己按照思路手打一遍。 其实是本代码设置了防抄袭（ 时间复杂度：O(T×nlog⁡n)O(T \times n \log n)O(T×nlogn)，AC。 4. 后续 今天刚考完 CSP，就不推题了。没做出 T2 我是不是炸了。

null

由于最多只有一个部门人数会超出n/2，所以先选择每人满意度最高的，把损失排序后依次减去