30分求助

12345limengqi @ 2023-11-10 15:51:54

#include <iostream>
#include <algorithm>
using namespace std;
unsigned long long int n, m;
unsigned long long int cc = 0;
unsigned long long int t;
unsigned long long int mm = 1000000;
int main () {
    cin >> m >> n;
     unsigned long long a[n];// 学生估分成绩 
     unsigned long long b[m];// 学校的预计录取分数 
    for(int i = 0; i < m; i++){
        cin >> b[i];
    }
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i] > b[j]){
                t = a[i] - b[j];    
            }
            else {
                t = b[j] - a[i];
            }
            if(mm > t){
                mm = t;
            }
        }
        cc += mm;
        mm = 1000000;
    }
    cout << cc;
    return 0;
}

by duqtomorrow @ 2023-11-10 16:26:59

我去没有取最小值，但是你这样做，还是会超时。用lower_bound，试一下，我一会儿写一个 for(int i = 0; i < n; i++){ mm = LLONG_MAX; for(int j = 0; j < m; j++){ if(a[i] > b[j]){ mm = min(a[i] - b[j],mm); } else { mm = min(b[j] - a[i],mm); } } cc += mm; }

by return0114514 @ 2023-11-10 16:30:23

用二分来做

by return0114514 @ 2023-11-10 16:32:34

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100001];
int b[100001];
long long ans=0;//注意开longlong
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>b[i];
    }
    sort(a+1,a+1+m);
    for(int i=1;i<=m;i++)
    {
        int l=1,r=n+1;
        while(l<r)
        {
            int mid=(l+r)/2;
            if(a[mid]<b[i])
            {
                l=mid+1;
            }
            else
            {
                r=mid;
            }
        }
        if(b[i]<a[1])
        {
            ans+=a[1]-b[i];
        }
        else
        {
            ans+=min(abs(a[l-1]-b[i]),abs(a[l]-b[i]));
        }
    }
    cout<<ans<<endl;
    return 0;
}

by duqtomorrow @ 2023-11-10 16:37:58

用lower_bound并注意是不是第一个。

#include <bits/stdc++.h>
using namespace std;
int n, m;
long long cc = 0;
long long mm = LLONG_MAX;
int main () {
    cin >> m >> n;
     long long a[n];// 学生估分成绩 
     long long b[m];// 学校的预计录取分数 
    for(int i = 0; i < m; i++){
        cin >> b[i];
    }
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    sort(b,b+m);
    for(int i = 0; i < n; i++){
        int pos=lower_bound(b,b+m,a[i])-b;
        if(pos>0){
            cc += min(abs(a[i]-b[pos]),abs(a[i]-b[pos-1]));
        }else{
            cc += abs(a[i]-b[pos]);
        }

    }
    cout << cc;
    return 0;
}

来拿 分了**

by 12345limengqi @ 2023-11-10 17:36:03

谢谢两位大佬 @duqtomorrow @shenrongcheng

by 12345limengqi @ 2023-11-10 17:39:27

已赏关注一枚