P1678求优化

学术版

Sp0523 @ 2024-11-28 21:08:19

P1678 谁能帮我优化一下(超时)
由于我太

#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 AzusidNya @ 2024-11-28 21:26:14

有了解过「时间复杂度」的概念吗?你的做法的时间复杂度是 O(nm) 的,在 n, m \le 10^5 的数据范围下本来就不应该通过。


by AzusidNya @ 2024-11-28 21:26:31

@Sp0523


by Sp0523 @ 2024-11-28 21:35:55

@AzusidNya 谢谢


|