题解：CF2037F Ardent Flames

__vector__ · 2024-11-21 12:47:42 · 题解

题意

有 n 个编号为 1 到 n 的奶龙在 x 坐标轴上，第 i 个奶龙的生命值为 h_i，横坐标为 x_i，保证奶龙们的横坐标按照其编号升序。

你可以预先选定一个横坐标 p，并发动任意次数强度为 m 的攻击。

每次攻击后，第 i 个奶龙受到 \max(0,m-|p-x_i|) 的伤害，当奶龙的生命值降到 0 及以下，这个怪物就被击败了。注意 p 在攻击前选定，且选定之后不能改变。

给定整数 n,m,h_i,x_i,k，求如何选择 p，使得能在最少的攻击次数内击杀至少 k 个奶龙。

只需要求出最少的攻击次数。

做法

显然答案具有单调性，可以二分答案，设当前二分的答案为 l。

考虑如何快速检查合法性。

注意到，此时需要判断是否存在一个坐标，使得其能击败至少 k 个奶龙。

考虑求出每个奶龙可以被打败的 p 区间。

对于第 i 个奶龙，打败它需要保证 l\cdot(m-|p-x_i|) \ge h_i。

得出 m-|p-x_i| \ge \frac{h_i}{l}。

即 -|p-x_i| \ge \lceil \frac{h_i}{l} \rceil+m。