上课的时候以为听懂了系列(然后发现其实啥都没懂)
# 题面
一个质量均匀分布的横梁由 $n+2$ 个高度相同的柱子支撑。柱子的位置可以抽象在数轴上,从左到右编号为 $0\sim n+1$,第 $i$ 个柱子在 $x_i$ 处,它的承重能力是 $d_i$;特别的,柱子 $0$ 和 $n+1$ 的承重能力为 $+\infty$。
对于相邻的两根柱子 $u$ 和 $v$,每根柱子承受它们之间的横梁的重量的一半。若一个柱子承受的重量超过其能力,它就会坍塌(消失)。
现在你要指定一个位置加一根柱子(承重能力自己指定),使得最后除了柱子 $0$ 和 $n+1$,还有柱子留下;特别的,如果加柱子的位置原本有柱子,原来的柱子就会被新柱子替换掉;并且你加的柱子的位置、承重能力都是非负实数。求加的柱子的最小承重能力。
数据规模:$1\le n\le10^5$,$0\le x_i,d_i\le10^9$。
# 解析
先判断是否一开始就可以有中间的柱子留下(判断方法后面写),如果是,则答案为 $0$。下面的解析默认忽略这种情况。
由于一段横梁的重量由相邻两个柱子分担,容易发现加入一根横梁的目的是阻止最终与它相邻的两个柱子坍塌,并且显然加入的柱子不会坍塌。
于是不妨决策加入柱子后,最终与这个柱子相邻的柱子是哪两个,记为 $L,R$。这样就可以分成前后缀考虑,即分别考虑加入的柱子左边和右边各自留下了哪些柱子。明显的,$L,R$ 是否合法以及加入的柱子的承重能力仅取决于 $L,R$。
对于柱子 $i$ 计算 “假设 $i$ 不会倒,则最终的方案中,$i$ 的左边是哪个柱子”,记为 flef[i]
;同理,右边的柱子记为 frig[i]
。考虑如何计算 flef[i]
。可以从左到右计算每根柱子,用栈维护当前有哪些柱子(栈顶就是现在剩下的柱子中最右边的)。计算 flef[i]
时,判断栈顶的柱子会不会坍塌,直到找到不会坍塌的柱子即为 flef[i]
,然后把 $i$ 入栈。
如果计算出来 flef[n+1]
不是 $0$,则说明不用加柱子就已经合法。
同理求得 frig[i]
后,可以求得,如果 $i$ 不坍塌
- 则 $i$ 右边至少在哪个位置要有柱子:$\frac{x-flef_i}2\le d_i\to x\le 2d_i+flef_i$;
- 则 $i$ 左边至少在哪个位置要有柱子:$\frac{frig_i-x}2\le d_i\to x\ge frig_i-2d_i$。
如果 $L,R$ 满足
则可以在 $L,R$ 之间放一根柱子使该方案合法。前两个不等式保证了 $L$ 左边的重量不会使 $L$ 坍塌、$R$ 右边的重量不会使 $R$ 坍塌,第三个不等式保证了存在一种在 $L,R$ 之间放柱子的方案使得 $L,R$ 都不坍塌。另外,可以看出无论在 $L,R$ 之间哪个位置加柱子,加的柱子的承重能力都是 $\frac{x_R-x_L}2$,于是只需要找合法的最小的 $x_R-x_L$。
双端点问题可以考虑枚举一个端点,比如 $R$;$R$ 确定后,就相当于是找最大的满足条件的 $L$。容易发现,如果 $L_2>L_1$ 并且 $flef_{L_2}+2d_{L_2}\ge flef_{L_1}+2d_{L_1}$,则 $L_1$ 一定就没有用了。于是可以从左到右扫描,用单调栈维护 $flef_i+2d_i$ 单减的序列,对于 $R$ 在单调栈上二分 $flef_i+2d_i\ge frig_R-2d_R$ 的最大 $i$。
# 源代码
1 | /*Lucky_Glass*/ |
THE END
Thanks for reading!
> Linked 何日重到苏澜桥-Bilibili