自动搬运

查看原文

来自洛谷，原作者为

	嘉然小姐的狗 头像：https://www.douban.com/group/topic/224486089/

搬运于2025-08-24 22:02:43，当前版本为作者最后更新于2020-07-23 11:57:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

翻阅了网上屈指可数的题解，似乎都没有提到决策的单调性的证明；因此本人于此补上证明。

对于只想看看决策单调性证明的人，请手动翻到下面的证明 2 一节。

对于想要到我的洛谷博客查看的人，请到这里。

---

前置知识：以点 $A$ 为圆心的半径为 $r_A$ 的圆，与以点 $B$ 为圆心的半径为 $r_B$ 的圆不相交的充要条件是

$$\text{dis}(A, B) \geq r_A + r_B$$

其中 $\text{dis}(A, B)$ 表示点 $A$ 到点 $B$ 的距离，$\text{dis}(A, B) = \sqrt {(x_A - x_B)^2 + (y_A - y_B)^2}$。

---

对于 $j < i$，圆 $j$ 和圆 $i$ 不相交的充要条件是

$$\begin{aligned} (r_i - r_j)^2 + (x_i - x_j)^2 &\geq (r_i + r_j)^2 \\ (x_i - x_j)^2 &\geq 4r_ir_j \\ r_i &\leq \frac {(x_i - x_j)^2}{4r_j} \ \\ \end{aligned} $$

在没有限制的情况下，可以得到

$$r_i = \min_{1 \leq j < i} \left\{\frac {(x_i - x_j)^2}{4r_j}\right\} $$

考虑如何求解。

定理 1：若 $x_i < x_j$ 且 $r_i \leq r_j$，则圆 $i$ 一定不会影响到 $j$ 后面的圆。即，对于 $k > j$ 有

$$\frac {(x_k - x_j)^2}{4r_j} < \frac {(x_k - x_i)^2}{4r_i} $$

证明 1：显然有 $(x_k - x_j)^2 < (x_k - x_i)^2$ 且 $r_j > r_i$，易证。

此时我们可以忽略圆 $i$。我们可以用一个单调栈维护它，使栈内从顶到底 $x_i$ 单调下降且 $r_i$ 单调上升。

下面考虑如何决策。

定理 2：对于栈内元素 $i < j$ 和当前决策点 $k$（$i < j < k$），若 $r_k < r_j$，则 $r_k$ 不会受到 $i$ 的影响。

更直白地，若一个气球的半径比前面某个气球 $j$ 的半径小，则它不会受到 $j$ 前面气球的影响。

证明 2：考虑证明 $r_j < \frac {(x_k - x_i)^2}{4r_i}$。这个证明是显然的：

$$r_k < r_j < \frac {(x_j - x_i)^2}{4r_i} < \frac {(x_k - x_i)^2}{4r_i} $$

也就是 $r_k < \frac {(x_k - x_i)^2}{4r_i}$，即 $r_k$ 不会受到 $j$ 之前气球 $i$ 的影响。

这一点保障了我们决策时只需要找出栈顶进行决策即可：

1. 取出栈顶 $j$ 对当前决策点 $k$ 进行决策；
2. 若 $r_k < r_j$，则它不会受前面的气球的影响了。把 $r_k$ 加入栈顶，退出；
3. 否则弹出栈顶 $j$（为了维护 $r_j$ 递增），回到 1。

stack.clear()
for i = 1 to n
    while stack is not empty
        j = stack.top
        r[i] = min(r[i], (x[i] - x[j]) * (x[i] - x[j]) / 4 / r[j])
        if r[i] < r[j] then
            break
        else
            stack.pop()
    stack.push(i)

时间复杂度：$O(n)$。