本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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$。

$|p-x_i| \le m-\lceil \frac{h_i}{l} \rceil $。

也就是说，第 $i$ 个奶龙会被打败当且仅当选定的坐标 $p$ 与这个奶龙距离不能超过 $m-\lceil \frac{h_i}{l} \rceil$。

计算出每个奶龙会被打败的 $p$ 区间，看下是否存在一个点被大于等于 $k$ 个区间覆盖就可以解决。此部分可以离散化再差分。