题解 P4697 【[CEOI2011]Balloons】

· · 题解

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

对于只想看看决策单调性证明的人，请手动翻到下面的证明 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)。