题解：CF2005B2 The Strict Teacher (Hard Version)

前言

第

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

。~~就因为这个我调了半小时。~~

代码

CPP

//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;
}

题解：CF2005B2 The Strict Teacher (Hard Version)

文章操作

前言

分析

好东西

注意

代码

相关推荐

评论

题解：CF2005B2 The Strict Teacher (Hard Version)