RonL @ 2024-05-30 21:42:38

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int m,n;
ll line[100005];
ll arr[100005];
bool check(ll x){
    ll ans = 0;
    ll minn;
    for(int i=1;i<=n;i++){
        minn = 99999999;
        for(int j=1;j<=m;j++){
            minn = min(minn,abs(line[j]-arr[i]));
        }
        ans += minn;
    }
    return ans <= x;
}
void solve(){
    cin >> m >> n;
    ll r = 0;
    for(int i=1;i<=m;i++){
        cin >> line[i];
    }
    for(int i=1;i<=n;i++){
        cin >> arr[i];
        r += arr[i];
    }
    ll l = 1;
    while(l < r){
        int mid = (l+r)/2;
        if(check(mid))r = mid;
        else l = mid+1;
    }
    cout << l;
}
int main(){
    solve();
    return 0;
}

by zldx @ 2024-07-18 15:15:04

@RonL ```

include<bits/stdc++.h>

using namespace std; typedef long long T;

int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); T n,m,sum=0; cin>>n>>m; vector<T>v1(n); vector<T>v2(m); for(T i=0;i<n;i++){ cin>>v1[i]; } sort(v1.begin(), v1.end()); for(T i=0;i<m;i++){ cin>>v2[i]; } sort(v2.begin(), v2.end()); for(T i=0;i<m;i++){ if(v2[i]<v1[0]){ sum+=v1[0]-v2[i]; continue; }if(v2[i]>v1[n-1]){ sum+=v2[i]-v1[n-1]; continue; } T r,l,mid; l=0; r=n-1; while(l<r){ mid=(l+r+1)/2; if((v1[mid]<v2[i]&&v1[mid+1]>v2[i])||(v1[mid]>v2[i]&&v1[mid-1]<v2[i])){ if(v1[mid]<v2[i]&&v1[mid+1]>v2[i]){ sum+=min(v2[i]-v1[mid],v1[mid+1]-v2[i]); break; }else{ sum+=min(v2[i]-v1[mid-1],v1[mid]-v2[i]); break; } }else{ if(v1[mid]<v2[i]){ l=mid+1; }if(v1[mid]>v2[i]){ r=mid-1; }if(v1[mid]==v2[i]){ break; } } } } cout<<sum; return 0; }

by zldx @ 2024-07-18 15:16:06

不好意思写错了 下面才是

by zldx @ 2024-07-18 15:16:27

@RonL

#include<bits/stdc++.h>
using namespace std;
typedef long long T;

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    T n,m,sum=0;
    cin>>n>>m;
    vector<T>v1(n);
    vector<T>v2(m);
    for(T i=0;i<n;i++){
        cin>>v1[i];
    }
    sort(v1.begin(), v1.end());
    for(T i=0;i<m;i++){
        cin>>v2[i];
    }
    sort(v2.begin(), v2.end());
    for(T i=0;i<m;i++){
        if(v2[i]<v1[0]){
            sum+=v1[0]-v2[i];
            continue;
        }if(v2[i]>v1[n-1]){
            sum+=v2[i]-v1[n-1];
            continue;
        }
        T r,l,mid;
        l=0;
        r=n-1;
        while(l<r){
            mid=(l+r+1)/2;
            if((v1[mid]<v2[i]&&v1[mid+1]>v2[i])||(v1[mid]>v2[i]&&v1[mid-1]<v2[i])){
                if(v1[mid]<v2[i]&&v1[mid+1]>v2[i]){
                    sum+=min(v2[i]-v1[mid],v1[mid+1]-v2[i]);
                    break;
                }else{
                    sum+=min(v2[i]-v1[mid-1],v1[mid]-v2[i]);
                    break;
                }
            }else{
                if(v1[mid]<v2[i]){
                    l=mid+1;
                }if(v1[mid]>v2[i]){
                    r=mid-1;
                }if(v1[mid]==v2[i]){
                    break;
                }
            }
        }
    }
    cout<<sum;
    return 0;
}