P13778 Solution

irris · 2025-10-13 21:37:18 · 题解

从另一个视角研究问题——考虑有哪些题目产生了贡献。在选出的题目产生贡献时，分别有 0, 1, 2, \ldots, \mathsf{Ans} - 1 个题目产生了贡献。于是对于一道具体的题目，如果之前已经有 t 个题目产生了贡献，那么其被选择的时间点应 恰好为 k - c_i + 2t + 1。所有被选择的题目应两两不同，且选择的时间点应当构成 [1, n] 内的单增序列。

贪心地，我们只需要找到一个最大的 \mathsf{Ans} 满足选择 \mathsf{Ans} 个题目，最后一次选择的时间不超过 n 即可（但这个问题的贡献计算有些特殊，如果有实际未产生贡献的位置产生了贡献，我们不考虑这次贡献，并不一定总是不劣的，也就是我们可能会得到比实际答案大的值。我们将会在最后修复这个漏洞）。

令 a_i = k - c_i + 1。如果取出了一个 a_i，则取出的下一个元素 a_j 必定满足 \color{blue}a_j \geq a_i - 1；而在取出的元素个数一定时，我们希望 最小化最后一个被取走元素的值。这个最小化工作是容易完成的：将 a_1, \ldots, a_n 排序，我们可以将其取值划分为若干个极长值域区间 [l_1, r_1], [l_2, r_2], \ldots, [l_m, r_m]，其中 r_i + 1 < l_{i+1}。设第 i 个区间内包含 c_i 个数，则若 \mathsf{Ans} \leq c_1，那么最后一个被取走元素的值的最小可能值为 l_1；若 \leq c_1 + c_2，则最小可能值为 l_2；依此类推。但需要注意的是，所有 r \leq 0 的区间 [l, r] 是无法被取走的，我们需要先删去这些值。于是此时检查某个 \mathsf{Ans} 是否合法是容易的，时间复杂度 O(n\log n)，瓶颈在排序上。

接下来我们将说明，在我们得到的最大 \mathsf{Ans} 处，一定存在一种对剩余题目的排列方式满足剩余题目不产生贡献。如果在所有产生贡献的题目后再产生一次贡献，则 \mathsf{Ans} 一定会更大；否则，由于我们取出的均为 a_i 所有可能产生贡献的一个前缀，那么一定不存在某个 a_j \geq a_i 但是比 a_i 在同一个前缀情况下优先产生贡献的情况。所以求出的 \mathsf{Ans} 确实是最优的。