题解

问题分析

在简单版本中，有 $m=2$ 位老师和 $q=1$ 个查询。我们需要计算在最优策略下，老师们抓住 David 所需的最少步数。

David 想最大化被抓的时间，老师们想最小化这个时间。由于所有人都能看到彼此的位置并最优行动，这是一个典型的追及问题。

核心思路

根据 David 相对于两位老师的位置，可以分为三种情况：

情况 1：David 在两位老师的左侧

即 David 的位置 $b$ 满足 $b < b_1$（$b_1$ 是左边老师的初始位置）。

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

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

情况 2：David 在两位老师的右侧

即 David 的位置 $b$ 满足 $b > b_2$（$b_2$ 是右边老师的初始位置）。

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

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

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

即 $b_1 < b < b_2$。

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

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

因此，所需时间为： $ans= \left\lfloor \frac{b_2 - b_1}{2} \right\rfloor $

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

算法步骤

1. 读入 $n, m, q$（这里 $m=2, q=1$）
2. 读入两位老师的位置 $b_1, b_2$ 并排序
3. 读入 David 的位置 $a$
4. 判断 David 相对于老师的位置：
   • 如果 $a < b_1$：输出 $b_1 - 1$
   • 如果 $a > b_2$：输出 $n - b_2$
   • 否则：输出 $(b_2 - b_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;  // m=2, q=1

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

        sort(a.begin(), a.end());  // 确保 a[0] ≤ a[1]

        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[1]
            else 
                cout << (a[k] - a[k - 1]) / 2 << ' '; // 情况3: a[0] < b < a[1]
        }
        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(2 \log 2) = O(1)$
• 每个查询 $O(\log m) = O(1)$
• 总复杂度 $O(t)$，可以处理 $t \le 10^5$ 的数据

示例验证

输入：

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

处理过程：

1. 第1个测试：$b_1=1, b_2=4, a=2$
   $a=2$ 在 $b_1$ 和 $b_2$ 之间 → $(4-1)/2 = 1.5$ 向下取整得 $1$

2. 第2个测试：$b_1=3, b_2=6, a=1$
   $a=1 < b_1$ → $b_1 - 1 = 2$

3. 第3个测试：$b_1=3, b_2=6, a=8$
   $a=8 > b_2$ → $n - b_2 = 8 - 6 = 2$

输出：

1
2
2

与示例输出一致。