题解：CF2005B2 The Strict Teacher (Hard Version)

Wide_Master · 2025-01-26 10:47:32 · 题解

前言

第 6 篇题解。

分析

我们可以分类讨论，明显发现，只有 David 两侧的老师或者墙有作用。同时，我们要先排序。

接下来我们开始分类讨论。

• 如果 David 的位置小于最左边的老师，那么他就可以一直往左移动，直到移动到墙，也就是说，在这种情况下，需要 b_1-1 步才能抓住 David。
• 如果 David 的位置大于最右边的老师，那么他就可以一直往右移动，直到移动到墙，也就是说，在这种情况下，需要 n-b_m 步才能抓住 David。
• 如果 David 的左边和右边都有老师，直到离的最近老师两面包夹，也就是说，在这种情况下，需要 (b_r-b_l)\div2 步才能抓住 David。这里的 l 代表离 David 最近且在左边的老师的编号，r 代表离 David 最近且在右边的老师的编号。这个过程可以用二分。

好东西

你可以不用手写二分，因为 C++ 里面自带了两个二分函数 lower_bound 和 upper_bound。

• lower_bound 能查找第一个小于你查找数字的地址符。
• upper_bound 能查找第一个大于等于你查找的数字的地址符。

注意

一定要搞清楚 n,m 代表者什么，不要搞混 n,m。就因为这个我调了半小时。

代码

//By xiaozhou001
#include<bits/stdc++.h>
using namespace std;
int t,n,m,q,b,a[100007];
int main()
{
    cin>>t;
    while(t--){
        cin>>n>>m>>q;
        for(int i=1;i<=m;i++){
            cin>>a[i];
        }
        sort(a+1,a+1+m);
        for(int i=1;i<=q;i++){
            cin>>b;
            if(b<a[1]){
                cout<<a[1]-1<<endl;
            }else if(b>a[m]){
                cout<<n-a[m]<<endl;
            }else{
                int l=lower_bound(a+1,a+1+m,b)-a;
                int r=upper_bound(a+1,a+1+m,b)-a-1;
                cout<<abs(a[r]-a[l])/2<<endl;
            }
        }
    }
    return 0;
}