求帮助

Sp0523 @ 2024-11-28 20:59:51

#include <bits/stdc++.h>
using namespace std;
long long n,m,dog=0;
int main(){
    cin>>n>>m;
    long long a[n],b[m];
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<m;i++){
        cin>>b[i];
        int q=1000000;
        for(int j=0;j<n;j++){
            if(abs(a[j]-b[i])<q){
                                q=abs(a[j]-b[i]);
                        }
        }
        dog+=q;
    }
    cout<<dog;
    return 0;
}

by iamsh @ 2024-11-28 21:07:40

这是哪道题目

by Sp0523 @ 2024-11-28 21:09:16

@iamsh P1678

by iamsh @ 2024-11-28 21:13:32

这道题像你这样写是 O(nm) 的，会超时
需要考虑优化，将学校的录取分数线排序，然后枚举学生，二分找到最接近学生成绩的学校

by iamsh @ 2024-11-28 21:38:14

@Sp0523 这是我的代码，可以参考一下

#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int n,m,a[N],b[N];
int main() {
    ios::sync_with_stdio(0);
    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 + m + 1);
    long long ans = 0;
    for(int i = 1;i <= n;i ++) {
        if(b[i] < a[1]) {//特判的情况
            ans += a[1] - b[i];
            continue;
        }
        if(b[i] > a[m]) {
            ans += b[i] - a[m];
            continue;
        }
        int x = lower_bound(a + 1,a + m + 1,b[i]) - a;//第一个大于等于的位置
        int t = min({abs(a[x] - b[i]),abs(a[x - 1] - b[i]),abs(a[x + 1] - b[i])});
        ans += t;
    }
    cout << ans;
    return 0;
}

没加特判会挂成 70 分，被卡了十分钟