超时，求调悬关！！！（我的二分总是超时，有什么方法判断吗

lucy2012 @ 2024-03-20 18:12:34

#include<bits/stdc++.h>
using namespace std;
int m,n,a[10000010],b[10000010],l=0,r=10000000,mid,sum=0;
int find(int num){
    int l=1,r=10000000;
    while(l<r){
        mid=l+r>>1;
        if(num>=mid)
            l=mid;
        else
            r=mid;
    }
    if(abs(a[l]-num)>abs(a[r]-num))
        return abs(a[r]-num);
    else
        return abs(a[l]-num);
}
int main(){
    cin>>m>>n;
    for(int i=1;i<=m;i++)
        cin>>a[i];
    sort(a+1,a+1+m);
    for(int i=1;i<=n;i++){
        cin>>b[i];
        sum+=find(b[i]);
    }
     cout<<sum;  
    return 0;
}   

by fight_for_humanity @ 2024-03-20 18:37:42

跑到 l+1 = r 的时候，mid 一直是 l，就死循环了

by lucy2012 @ 2024-03-20 18:47:11

@fight_for_humanity 该怎么改？QAQ

by lucy2012 @ 2024-03-20 18:55:53

这样不超时但是错的

#include<bits/stdc++.h>
using namespace std;
int m,n,a[10000010],b[10000010],l=0,r=10000000,mid,sum=0;
int find(int num){
    int l=1,r=10000000;
    while(l<r){
        mid=l+r>>1;
        if(num>=a[mid])
            l=mid+1;
        else
            r=mid-1;
    }
    if(abs(a[l]-num)>abs(a[r]-num))
        return abs(a[r]-num);
    else
        return abs(a[l]-num);
}
int main(){
    cin>>m>>n;
    for(int i=1;i<=m;i++)
        cin>>a[i];
    sort(a+1,a+1+m);
    for(int i=1;i<=n;i++){
        cin>>b[i];
        sum+=find(b[i]);
    }
     cout<<sum;  
    return 0;
}   

by fight_for_humanity @ 2024-03-20 22:12:08

二分得到的结果 l 的意义是在 a 数组里找到的第一个大于等于 num 的位置，结果应该取 l 和 l-1 的，同时注意特判 l == 0 的情况