远亲不如近邻

普通解法

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

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;
}

最优解法

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

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;
}