题解：CF2005B2 The Strict Teacher (Hard Version)

cyntmeay · 2025-09-09 18:20:17 · 题解

题目大意

在一个长度为 n 的数轴上有 m 个老师，给出 q 次询问，每每次询问一个学生的位置 p。每一回合学生先集体移动一个单位，然后老师再移动一个单位，可以选择不移动，求最后可以抓到多少个学生。

题目解法

• 如果一个学生有一端（左边或者右边）没有一个老师哪么就一直往没有老师的方向走，一直到尽头不动让老师尽可能晚的抓到自己就是最优解。
• 如果一个学生两边都有老师，哪么到两个老师的正中间等死就行。

如何找到老师位置

使用二分查找快速确定老师位置。

给出代码

#include<bits/stdc++.h>
using namespace std;
int T,n,m,q,b[100001],a,l,r,lef,rig,mid,ans;
int main(){
    scanf("%d",&T);//注意有多组数据
    while(T --){
        scanf("%d%d%d",&n,&m,&q);
        for(int i = 1;i <= m;i ++){
            scanf("%d",&b[i]);
        }
        sort(b + 1,b + m + 1);
        for(int i = 1;i <= q;i ++){
            scanf("%d",&a);
            l = 0,r = m;
            while(l < r){//二分查找
                mid = l + r + 1 >> 1;
                if(b[mid] < a){
                    l = mid;
                }
                else{
                    r = mid - 1;
                }
            }
            if(!l){
                ans = b[1] - 1;
            }
            else if(l == m){
                ans = n - b[m];
            }
            else{
                lef = b[l];
                rig = b[l + 1];
                if((rig - lef) % 2 == 1){
                    ans = (rig - lef - 1) / 2; 
                }
                else{
                    ans = (rig - (rig + lef >> 1));
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}