求助！关注为回报

天下为公 @ 2021-10-12 22:50:01

#include<bits/stdc++.h>
using namespace std;
long long q,w,a[100000005],b,ans=0;
int main()
{
    cin>>q>>w;
    for(int i=1;i<=q;i++) cin>>a[i];
    sort(a+1,a+q+1);
    for(int i=1;i<=w;i++){
        cin>>b;
        int left=1,right=q;
        while(left<right){
            int mid=(left+right)/2;
            if(a[mid]>=b){
                right=mid;
            }
            else{
                left=mid+1;
            }
        if(left==1) ans+=abs(b-a[1]);
        else ans+=min(abs(b-a[left-1]),abs(b-a[left]));
    }  
}
    cout<<ans;
    return 0;
}

by YGB_XU @ 2021-10-13 00:15:34

建议用这个模板：

int l,r,mid,ans=-1;
while(l<=r){
    mid=(l+r)/2;
    if(check(mid)) ans=mid,(l=mid+1 or r=mid-1);
    else (r=mid-1 or l=mid+1);
}

保证正确性，而且能判断一些无解的情况（ans 初值为 -1）。

您的代码修改后如下：

int left=1,right=q,find=-1;//find表示找到的符合条件的下标中最小的
        while(left<=right){
            int mid=(left+right)/2;
            if(a[mid]>=b) right=mid-1,find=mid;//满足条件(大于等于b),更新find值
            else left=mid+1;
        }
        if(find==1) ans+=abs(b-a[1]);
        else if(find==-1) ans+=abs(b-a[q]);//没找到,即a中数全部比b小,需要特判
        else ans+=min(abs(b-a[find-1]),abs(b-a[find]));

by YGB_XU @ 2021-10-13 00:16:35

@天下为公

by kdy20100729 @ 2021-10-14 08:46:45

@天下为公
下面是我的代码：

#include<bits/stdc++.h>
using namespace std;
int m,n,sum=0;
double a[100005],b[100005];
double help(double x)
{
    int l=1,r=m;
    while(l+1<r)
    {
        int mid=(l+r)/2;
        if (a[mid]==x)
            return 0;
        else if(a[mid]<x)
            l=mid;
        else
            r=mid;
    }
    if (abs(a[l]-x)<=abs(a[r]-x))
        return abs(a[l]-x);
    else
        return abs(a[r]-x);
}

int main()
{
    cin >> m >> n;
    for(int i=1; i<=m; i++)
        cin >> a[i];
    for(int i=1; i<=n; i++)
        cin >> b[i];
    sort(a+1,a+m+1);
    for(int i=1; i<=n; i++)
        sum+=help(b[i]);
    cout << sum;
    return 0;
}

by YGB_XU @ 2021-10-15 01:06:20

请问贴主还在吗……