左转去洛谷，全站公开的题解必须康康点个赞。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
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×nlogn)O(T \times n \log n)O(T×nlogn)，AC。
4. 后续
今天刚考完 CSP，就不推题了。没做出 T2 我是不是炸了。
