让你失望了私人教师 Kuroni

· · 题解

As a professional private tutor, Kuroni has to gather statistics of an exam. Kuroni has appointed you to complete this important task. You must not disappoint him.

私人老师让我来完成这道私人题目。

para 太牛了，但是为什么这道题的练习题目是 Teoretičar。

有 n 个问题，m 个人，g_i 表示第 i 个人的得分，已知 q 个人的得分：排名为 p_i 的人得分为 s_i，m 个人总得分为 t。f_i 表示第 i 个问题的答对人数，第 i 个问题至少 l_i 个人答对，至多 r_i 个人答对。现在可以列出已知条件：

g_{p_i}=s_i l_i \leq f_i \leq r_i \sum_{i=1}^{n}f_i=\sum_{i=1}^{m}g_i=t g_i \geq g_{i+1}

因为构成完美匹配，根据霍尔定理：一个二分图 (V1,V2,E) 存在完美匹配当且仅当 \forall_{S\in V1} |N(S)| \geq |S|，设 S 中有 k 个人，第 i 个人得分为 g'_i，可得：

\sum_{i=1}^{n}\min (f_i,k) \geq \sum_{i=1}^{k}g'_i

由于

\sum_{i=1}^{k}g'_i \leq \sum_{i=1}^{k}g_i

所以 g'_i=g_i 时限制最强，因此：

\sum_{i=1}^{n}\min (f_i,k) \geq \sum_{i=1}^{k}g_i

令 G_i 表示前 i 个人得分之和的最大值，可以根据上述推得：

G_i \leq \sum_{j=1}^{n}\min(f_j,i)

同时，由于已知 q 个人的得分，可以加强限制：

G_i = \min(G_i,G_{i+1}-\max_{j=1}^{q}[ p_j\geq i+1]s_j)

如果 f_i 确定，那么可以二分排第一的人数，然后为满足条件：

\sum_{i=1}^{m}g_i=t

根据 G_i 贪心的填即可。

现在考虑构造最优的 f_i。

由于要最大化排第一的人数，G_n=t，所以要最小化一段前缀的 G_i。因此为最小化

\sum_{j=1}^{n}\min(f_j,i) $$l_i \leq f_i \leq r_i$$ 的条件下尽可能地小且平均。 实现方面，将题目按照 $l_i$ 从小到大排序，先将通过人数都设为 $l_i$，计算剩余值，每次要补平一段前缀，用剩余值平均分配，同时用一个优先队列维护 $r_i$，每次将预期补平值超过 $r_i$ 的踢出即可，时间复杂度 $O(n \log n)$。 [code](https://codeforces.com/problemset/submission/1305/304639329)