【求调】答辩代码10pts，大佬勿喷

roumeideclown @ 2023-09-14 22:11:40

#include<bits/stdc++.h>
#pragma G++ optimize(2)
using namespace std;
int n,m,a[100001],b[100001],ans;
int abs_(int x) {
    return x>=0?x:-x;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    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+1+n);
    int l,r,mid,t;
    for(int i=1;i<=n;i++) {
        l=1,r=m,t=1e9;
        while(l<=r) {
            mid=(l+r)>>1;
            if(abs_(a[mid]-b[i])<t) {
                t=abs_(a[mid]-b[i]);
            }
            if(a[mid]<b[i]) {
                l=mid+1;
            }
            else {
                r=mid-1;
            }
        }
        ans+=t;
    }
    cout<<ans;
    return 0;
}

by __yun__ @ 2023-09-14 22:16:42

@roumeideclown
要考虑边界（即比最大值大和比最小值小）。
贴一下我的代码：

#include<bits/stdc++.h>
using namespace std;
const int M=1e6+10;
int n,m,a[M];
long long ans;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    int x;
    while(m--){
        cin>>x;
        int l=1,r=n,mid;
        while(l<=r){
            mid=(l+r)/2;
            if(a[mid]<=x) l=mid+1;
            else r=mid-1;
        }
        if(r==0) ans+=a[r+1]-x;
        else if(r==n) ans+=x-a[r];
        else ans+=min(x-a[r],a[r+1]-x);
    }
    cout<<ans;
    return 0;
}

by ccjjxx @ 2023-09-14 22:38:20

二分我是这么写的（\text{STL}大法）

for(int i=1;i<=n;i++)
    {
        int t=b[i];
        int low=lower_bound(a+1,a+m+1,t)-a;
        if(low==m+1)
        {
            ans+=t-a[m];
        }
        else if(low==1)
        {
            ans+=a[1]-t;
        }
        else
        {
            ans+=min(abs(a[low]-t),abs(a[low-1]-t));
        } 
    }