远亲不如近邻_牛客博客

普通解法

对于每个方案位置，暴力枚举所有居民位置。时间复杂度 $O(nm)$ ,空间复杂度 $O(1)$ .

vector<int> solve(int n, int m, vector<int> a, vector<int> x){
    vector<int> t(m);
    for(int i = 0; i < m; ++i){
        t[i] = 2e9;
        for(int j = 0; j < n; ++j) t[i] = min(t[i], abs(x[i]-a[j]));
    }return t;
}

最优解法

首先对所有居民位置排序。时间复杂度 $O(nlog(n))$
然后对于每个方案 $x_i$ ，在排好序的数组中二分查找最小的大于等于 $x_i$ 的位置和最大的小于等于 $x_i$ 的位置。单次查询复杂度 $O(logn(n))$
总的时间复杂度 $O((n+m)log(n))$

vector<int> solve(int n, int m, vector<int> a, vector<int> x){
    sort(a.begin(), a.end());
    vector<int> t(m);
    for(int i = 0; i < m; ++i){
        int val = x[i];
        int ans = 2e9;
        if(val < a[0]) ans = a[0]-val;
        else{
            int l = 0, r = n-1;
            while(l <= r){
                int mid = (r+l)>>1;
                if(a[mid] <= val){ans = min(ans, val-a[mid]); l = mid+1;}
                else r = mid-1;
            }
        }
        if(val > a[n-1]) ans = min(ans, val-a[n-1]);
        else{
            int l = 0, r = n-1;
            while(l <= r){
                int mid = (r+l)>>1;
                if(a[mid] >= val){ans = min(ans, a[mid]-val); r = mid-1;}
                else l = mid+1;
            }
        }
        t[i] = ans;
    }return t;
}