题意简述

有 $n$ 个敌人，第 $i$ 个敌人生命值 $h_i$，位置 $x_i$（严格递增）。
玩家选择一个整数位置 $p$（可以与敌人重合），然后每次攻击：

• 对距离 $p$ 为 $d$ 的敌人造成 $\max(0, m-d)$ 伤害，其中 $m$ 是攻击力。

问：最少攻击次数，使得存在某个 $p$，至少 $k$ 个敌人被击败（生命 $\le 0$）。
如果不存在这样的 $p$，输出 $-1$。

---

核心思路

直接枚举攻击次数 $q$ 然后判断是否可行。
因为 $q$ 越大越容易满足，所以可以二分答案。

---

二分可行性判断

假设我们固定攻击次数为 $q$（即二分中的 $mid$）。

$1$. 判断一个敌人能否在 $q$ 次攻击内被击败

设需要 每次攻击至少造成的伤害 为：

$$\text{need} = \lceil \frac{h_i}{q} \rceil$$

因为 $q$ 次总伤害需要 $\ge h_i$。

如果 $\text{need} > m$，则不可能击败该敌人（因为最大单次伤害为 $m$）。
否则，该敌人可被击败。

$2$. 可击败敌人对应的 $p$ 范围

每次攻击对位置 $x_i$ 的敌人伤害为 $m - |p - x_i|$，需要：

$$m - |p - x_i| \ge \text{need}$$

即：

$$|p - x_i| \le m - \text{need}$$

因此 $p$ 必须在区间：

$$[x_i - (m - \text{need}), \; x_i + (m - \text{need})] $$

---

$3$. 转化为区间覆盖问题

每个可击败的敌人对应一个整数区间 $[L_i, R_i]$，其中：

$$L_i = x_i - (m - \text{need}), \quad R_i = x_i + (m - \text{need}) $$

注意：$p$ 可以是任意整数，所以区间端点需取整，但这里 $x_i$ 和 $m - \text{need}$ 都是整数，所以 $L_i, R_i$ 都是整数。

问题变为：
是否存在一个整数点 $p$，被至少 $k$ 个这样的区间覆盖？

---

$4$. 区间覆盖计数（扫描线）

用差分思想：

• 对每个区间 $[L, R]$：
  • 在 $L$ 处 $+1$
  • 在 $R+1$ 处 $-1$（表示离开区间）

然后按位置从小到大扫描，累加覆盖数，一旦 $\ge k$ 则可行。

---

$5$. 二分边界

• 下界 $lo = 0$（不可能，但作为起始）
• 上界 $hi$ 可以设一个足够大的数，比如 $10^{10}$。

但标程中说明：
最大答案不会超过 $\max(h_i)$，因为攻击一次至少造成 $1$ 点伤害。
所以如果 $hi = 10^9$ 仍不可行，输出 $-1$。

---

$6$. 复杂度

• 二分：$O(\log(\max h))$
• 每次判断：$O(n \log n)$（排序事件，用 $map$ 或离散化）
• 总：$O(n \log n \log (\max h))$，可过。

---

$7$. 对应代码逻辑（C++ 版）

ll lo = 0, hi = 1e10;  // 上界设大一点
while (hi - lo > 1) {
    ll mid = (lo + hi) / 2;
    map<ll, int> ev;

    for (int i = 0; i < n; i++) {
        ll need = (h[i] + mid - 1) / mid;  // ceil(hi / mid)
        if (need > m) continue;

        ll left = x[i] - m + need;
        ll right = x[i] + m - need + 1;  // 开区间右端点
        ev[left]++;
        ev[right]--;
    }

    ll sum = 0;
    bool ok = false;
    for (auto& [pos, delta] : ev) {
        sum += delta;
        if (sum >= k) {
            ok = true;
            break;
        }
    }

    if (ok) hi = mid;
    else lo = mid;
}

---

$8$. 最终答案

如果 $hi == 1e10$ 说明不可行，输出 $-1$，否则输出 $hi$。

---

$9$. 样例验证

以第一个样例为例：

• $n=5,m=5,k=3$
  $h=[7,7,7,7,7]$
  $x=[1,2,3,4,5]$

二分 $mid=2$：

• $need = \lceil 7/2 \rceil = 4$
• $m-need = 1$
• 敌人 $i$ 区间：$[x_i - 1, x_i + 1]$
  • 敌人$1$: $[0,2]$
  • 敌人$2$: $[1,3]$
  • 敌人$3$: $[2,4]$
  • 敌人$4$: $[3,5]$
  • 敌人$5$: $[4,6]$

扫描线：

• 位置$2$ 被敌人$1$,$2$,$3$ 覆盖，共$3$个 $\ge k$，可行。

所以 $mid=2$ 可行，继续二分更小值，发现 $mid=1$ 不可行，答案 $2$。

---

$10$. 注意点

• 区间右端点处理成开区间，避免重复计数边界。
• $p$ 是整数位置，所以 $L,R$ 直接取整。
• 若 $\text{need} > m$，该敌人永远无法在 $q$ 次内击败，直接跳过。

---