题解

问题分析

在困难版本中，$m$ 和 $q$ 都可以达到 $10^5$，所有测试用例中 $m$ 的总和与 $q$ 的总和均不超过 $2 \times 10^5$。我们需要处理多个老师的情况，并回答 $q$ 个关于 David 位置的查询。

与简单版本类似，David 想最大化被抓的时间，老师们想最小化这个时间。关键在于确定 David 相对于老师们的区间位置。

---

核心思路

将老师的位置排序后，David 的位置相对于老师集合可以分为三种情况：

---

情况 1：David 在所有老师左侧

即 David 的位置 $a$ 满足 $a < b_1$（$b_1$ 是最左边的老师）。

在这种情况下，David 的最佳策略是尽可能向左逃，最远可以到达格子 $1$。最左边的老师需要从 $b_1$ 移动到 $1$，距离为 $b_1 - 1$。其他老师虽然也在追，但最左边的老师会最先抓住 David。

因此，所需时间为： $ans= b_1 - 1$

---

情况 2：David 在所有老师右侧

即 David 的位置 $a$ 满足 $a > b_m$（$b_m$ 是最右边的老师）。

类似地，David 的最佳策略是尽可能向右逃，最远可以到达格子 $n$。最右边的老师需要从 $b_m$ 移动到 $n$，距离为 $n - b_m$。

因此，所需时间为： $ans= n - b_m$

---

情况 3：David 在两位老师之间

即存在某个 $k$（$1 \le k < m$），使得 $b_k < a < b_{k+1}$。

此时，David 的最佳策略是移动到这两个老师之间的中间位置。由于这两位老师从两侧同时逼近，David 可以停留在中间，使两位老师需要相同的步数才能同时到达。

两位老师之间的初始距离为 $b_{k+1} - b_k$。当 David 位于正中间时，两位老师各需移动 $\frac{b_{k+1} - b_k}{2}$ 步（如果距离为奇数，则中间有两个格子，选择任意一个均可）。

因此，所需时间为： $ans= \left\lfloor \frac{b_{k+1} - b_k}{2} \right\rfloor$

注意：在代码中直接使用整数除法 $(b_{k+1} - b_k) / 2$ 即可，因为 C++ 整数除法会自动向下取整。

关键观察：David 位于哪两个老师之间是重要的，因为不同的相邻老师对之间的间隔不同，David 会移动到该间隔的中间位置，而时间取决于该间隔的长度。David 初始位置并不影响最终结果（只要他在该间隔内），因为他可以移动到中间位置。

---

算法步骤

1. 读入 $n, m, q$
2. 读入 $m$ 个老师的位置并排序
3. 对于每个查询 $a$：
   • 使用二分查找找到第一个大于等于 $a$ 的老师位置 $b_k$
   • 如果 $k = 0$（$a$ 小于所有老师）：输出 $b_0 - 1$
   • 如果 $k = m$（$a$ 大于所有老师）：输出 $n - b_{m-1}$
   • 否则（$a$ 在 $b_{k-1}$ 和 $b_k$ 之间）：输出 $(b_k - b_{k-1}) / 2$

---

标程解析

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t; cin >> t;  // 测试用例数

    while (t--) {
        int n, m, q; cin >> n >> m >> q;

        vector<int> a(m);
        for (int i = 0; i < m; i++) cin >> a[i];

        sort(a.begin(), a.end());  // 排序老师位置

        for (int i = 1; i <= q; i++) {
            int b; cin >> b;
            
            // 找到第一个大于等于 b 的老师位置
            int k = upper_bound(a.begin(), a.end(), b) - a.begin();

            if (k == 0) 
                cout << a[0] - 1 << ' ';           // 情况1: b < a[0]
            else if (k == m) 
                cout << n - a[m - 1] << ' ';       // 情况2: b > a[m-1]
            else 
                cout << (a[k] - a[k - 1]) / 2 << ' '; // 情况3: a[k-1] < b < a[k]
        }
        cout << "\n";
    }
    return 0;
}

代码说明：

• upper_bound 返回第一个大于 $b$ 的老师位置，$k$ 表示该老师的索引
• 若 $k=0$，说明 $b$ 比所有老师都小（情况1）
• 若 $k=m$，说明 $b$ 比所有老师都大（情况2）
• 否则，$b$ 在 $a[k-1]$ 和 $a[k]$ 之间（情况3）

---

复杂度分析

• 每个测试用例排序老师位置：$O(m \log m)$
• 每个查询二分查找：$O(\log m)$
• 所有测试用例的总复杂度：$O(\sum m \log m + \sum q \log m)$
• 由于 $\sum m \le 2 \times 10^5$，$\sum q \le 2 \times 10^5$，总复杂度可接受

---

示例验证

输入：

2
8 1 1
6
3
10 3 3
1 4 8
2 3 10

处理过程：

测试用例 1：

• $n=8, m=1, a=[6]$
• 查询 $b=3$：$k = \text{upper\_bound}([6], 3) = 0$（因为 $3 < 6$）
• 情况1：输出 $a[0] - 1 = 6 - 1 = 5$

测试用例 2：

• $n=10, m=3, a=[1,4,8]$（已排序）
• 查询 $b=2$：$k = \text{upper\_bound}([1,4,8], 2) = 1$（$a[1]=4 > 2$）
• 情况3：输出 $(a[1] - a[0]) / 2 = (4 - 1) / 2 = 1$
• 查询 $b=3$：$k = \text{upper\_bound}([1,4,8], 3) = 1$
• 情况3：输出 $(4 - 1) / 2 = 1$
• 查询 $b=10$：$k = \text{upper\_bound}([1,4,8], 10) = 3 = m$
• 情况2：输出 $n - a[2] = 10 - 8 = 2$

输出：

5
1
1
2

与示例输出一致。

---

关键结论

1. David 的最佳策略总是移动到最近的"安全区间"的中间位置
2. 对于左侧或右侧的区间，边界是 $1$ 或 $n$
3. 对于中间的区间，边界是相邻的老师
4. 答案只取决于区间长度，与 David 的初始位置无关（只要他在该区间内）
5. 使用二分查找快速定位 David 所在的区间