70pts球调qwq!!!

Sunnnnnn @ 2024-07-16 21:12:17

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

by Yk19820303 @ 2024-07-16 22:02:02

这道题涉及贪心算法，不能只用二分去做

by Yk19820303 @ 2024-07-16 22:03:43

具体代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100100],tot,x;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    while(m--){
        cin>>x;
        int r=n+1,l=0;
        while(l<r){
            int mid=(l+r)/2;
            if(a[mid]>=x) r=mid;
            else l=mid+1;
        }
                //这里需要用到贪心的思想
        if(x<=a[1]) tot+=a[1]-x;
        else tot+=min(abs(a[l-1]-x),abs(a[l]-x));
    }
    cout<<tot;
    return 0;
}

by Yk19820303 @ 2024-07-16 22:04:19

最后一个加测点可以加一个特判