P8424 题解

qbf！ · 2025-02-14 21:30:14 · 题解

首先有 mid=\dfrac{\sum_{i=1}^na_i}n 必定被包含。

对于每个 i，我们找到操作 i 次后重心位置 \le mid 且最大的区间，设其重心为 L_i，以及重心位置 \ge mid 且最小的区间，设其重心为 R_i。

我们大胆猜测题目相当于对每个 i 选择 c_i=L_i 或 c_i=R_i，然后最小化序列 c 的极差，证明如下：

假设 L_i 对应的区间为 [l,r-1]，R_i 对应的区间为 [l+1,r]，那么容易发现 [l+1,r-1] 必定是 L_{i+1} 或 R_{i+1}，假设它是 L_{i+1}：

• 假设我们选择了 c_i=L_i 且 c_{i+1}=L_{i+1}，那么我们显然可以从 [l,r-1] 走到 [l+1,r-1]。
• 假设我们选择了 c_i=L_i 且 c_{i+1}=R_{i+1}，那么由于 L_i<L_{i+1}，故我们显然可以把 c_{i+1} 调整成 L_{i+1} 而不会使答案更劣。
• 假设我们选择了 c_i=R_i 且 c_{i+1}=R_{i+1}，则我们显然可以从 [l+1,r] 走到 [l+2,r]。
• 假设我们选择了 c_i=R_i 且 c_{i+1}=L_{i+1}，则我们显然可以从 [l+1,r] 走到 [l+1,r-1]。