CF1764E Doremy's Number Line

Alex_Wei · 2022-11-29 14:12:29 · 题解

显然，当 a_1 \geq k 时有解， a_1 + b_1 < k 时无解。此时有 a_1 < k 且 a_1 + b_1 \geq k，则 p_1 不可能为 1，我们将 (a_1, b_1) 删去。

首先，因为可以点亮负数，所以 x 必须未点亮这个限制可以当做不存在。

进一步地，如果 x 可以被点亮，则任何小于 x 的位置均可被点亮，这一点根据对 x 的限制容易证明。因此，除了 p_1，其它 p_i 对应的 (a_{p_i}, b_{p_i}) 都是尽量往数轴右侧扩张，使得可扩张到不小于 k - b_1 的位置，若可以则有解，否则无解。

枚举 p_1，设 c 表示当前扩张的位置，则接下来的每个 (a, b) 都相当于 c\gets \min(a, c) + b。感性理解我们会先花掉 a 较小的 (a, b) 尽量扩张，使得花较大的 (a, b) 时 \min(a, c) 的限制尽量小。严谨证明直接考虑邻相交换即可。

不妨设 a_i \leq a_{i + 1}。

直接做的复杂度为 \mathcal{O}(n ^ 2)。但是若 p_1 = k，则所有 j < k 的 (a_j, b_j) 都会对 c 产生 a_j + b_j 的贡献。因此从小到大枚举 k，维护 a_j + b_j 的前缀 \max，即可求出 p_1 = k 时处理前 k 个 (a, b) 之后得到的 c。和 p_1 < k 时处理前 k - 1 个 (a, b) 得到的最大的 c 在经过 (a_k, b_k) 更新后的值取 \max 即可，可以看成一种动态规划。

时间复杂度 \mathcal{O}(n\log n)。代码。