「POI2011 R1」避雷针 Lightning Conductor 题解

题目解析

我们有一条街上的 $n$ 座建筑物，高度分别为 $h_1, h_2, \ldots, h_n$。如果要在第 $i$ 座建筑物上放置避雷针，其高度 $p_i$ 必须满足对于所有建筑物 $j$：

$$h_j \leq h_i + p_i - \sqrt{|i-j|}$$

整理后得到：

$$p_i \geq h_j - h_i + \sqrt{|i-j|} \quad \text{对所有 } j $$

因此对于每个 $i$，我们需要计算：

$$P_i = \max_{1 \leq j \leq n} \{ h_j - h_i + \sqrt{|i-j|} \} $$

由于 $p_i$ 必须是非负整数，最终答案就是 $\lceil P_i \rceil$。

问题转化

定义：

$$f(i) = \max_{1 \leq j \leq n} \{ h_j + \sqrt{|i-j|} \} $$

那么：

$$P_i = f(i) - h_i$$

问题转化为：对于每个 $i$，计算 $f(i) = \max\{ h_j + \sqrt{|i-j|} \}$。

算法思路

关键观察

函数 $h_j + \sqrt{|i-j|}$ 具有决策单调性。这意味着：

如果对于位置 $i$，$j$ 是最优决策点，那么对于位置 $i+1$，最优决策点 $j'$ 满足 $j' \geq j$。

分治优化

利用决策单调性，我们可以使用分治法来高效计算所有 $f(i)$：

1. 分离绝对值：将问题分解为两个子问题：

   • 左边：$f_L(i) = \max_{1 \leq j \leq i} \{ h_j + \sqrt{i-j} \}$
   • 右边：$f_R(i) = \max_{i \leq j \leq n} \{ h_j + \sqrt{j-i} \}$

   然后 $f(i) = \max(f_L(i), f_R(i))$

2. 分治求解：对于 $f_L(i)$，我们递归处理：

   • 在区间 $[l, r]$ 上，已知最优决策点范围在 $[L, R]$
   • 取中点 $mid = \frac{l+r}{2}$，在 $[L, R]$ 中找到 $mid$ 的最优决策点 $k$
   • 递归处理 $[l, mid-1]$（决策点在 $[L, k]$）和 $[mid+1, r]$（决策点在 $[k, R]$）

3. 复杂度分析：每个递归层总共扫描 $O(n)$ 个位置，共 $O(\log n)$ 层，总复杂度 $O(n \log n)$。

解题过程

步骤1：预处理

• 读取建筑物高度数组 $h[1 \ldots n]$

步骤2：计算左边贡献 $f_L$

• 使用分治法计算对于每个 $i$，$\max_{j \leq i} \{ h_j + \sqrt{i-j} \}$
• 维护当前递归区间和对应的决策点范围

步骤3：计算右边贡献 $f_R$

• 同样使用分治法计算对于每个 $i$，$\max_{j \geq i} \{ h_j + \sqrt{j-i} \}$
• 方法与左边对称

步骤4：合并结果

• 对于每个 $i$，$f(i) = \max(f_L(i), f_R(i))$
• $P_i = \lceil f(i) - h_i \rceil$，确保非负

算法特点

• 时间复杂度：$O(n \log n)$，适用于 $n \leq 5 \times 10^5$
• 空间复杂度：$O(n)$
• 核心技巧：利用决策单调性进行分治优化，避免了 $O(n^2)$ 的暴力计算

这种方法高效地解决了原本看似需要 $O(n^2)$ 时间的问题，是决策单调性优化的经典应用。