10分求助(二分答案)

P1678 烦恼的高考志愿

zhubaot @ 2023-01-10 22:26:32

#include<iostream>
#include<algorithm>
using namespace std;
int m,n,a[100010],q;
long long s;
int find(int x){
    int l=1,r=m,mid;
    while(l<=r){
        mid=(l+r)/2;
        if(x<a[mid])r=mid-1;
        else l=mid+1;
    }
    return r;
}
int main(){
    cin>>m>>n;
    for(int i=1;i<=m;i++)cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        cin>>q;
        int k=find(q);
        if(q<=a[1]){
            s+=a[1]-q;
            continue;
        }
        if(q>=a[m]){
            s+=q-a[m];
            continue;
        }
        if(a[k+1]-q>=q-a[k]){
            s+=q-a[k];
        }
        else s+=a[k+1]-q;
    }
    cout<<s;
    return 0;
}

by castal_ @ 2023-01-11 10:18:39

@zhubaot

第一个问题:二分判断写错了,应该是

a[mid] >= x;

第二个问题:返回值写错了,应该返回l,而不是r。因为你找的是第一个大于等于x的数,所以你只能返回l,

第三个问题:排序a数组时范围写错了,应该是

sort(a+1,a+1+m);

第四个问题:在最后返回k左右值判断的那里有问题,你那样写出出现负数,可以直接改成

s += min(abs(a[k-1]-q),abs(a[k]-q));

最后,建议你可以重新去推一推各种情况下的二分的判断条件,免得下次做题的时候一头雾水


|