首先对heater进行排序,对于每个house,我们尝试用二分的方式寻找它两端的heater去覆盖,取其中最小的,再与答案取最大值以求将每个house都覆盖到。
对于端点我们需要采取特殊处理,即左端点用最小的heater去覆盖,右端点用最大的heater去覆盖。

#include <bits/stdc++.h>
#define f(a,b,c) for(int a=b;a<c;++a)
#define MAXN 25000
using namespace std;

int n,m;
vector<int> heaters;
vector<int> houses;

int main() {
    ios::sync_with_stdio(false);

    cin >> n >> m;

    heaters.resize(m);
    houses.resize(n);

    int temp;
    f(i,0,n) {
        cin >> temp;
        houses.push_back(temp);
    }

    f(i,0,m) {
        cin >> temp;
        heaters.push_back(temp);
    }

    sort(heaters.begin(),heaters.end());
    
    int ans = INT_MIN;

    for(auto house : houses) {
        auto pos = lower_bound(heaters.begin(),heaters.end(),house);
        auto dist1 = (pos == heaters.end()) ? INT_MAX : *pos - house;
        auto dist2 = (pos == heaters.begin()) ? INT_MAX : house - *(--pos);

        ans = max(ans,min(dist1,dist2));
    }

    cout << ans << endl;

    return 0;
}
Last modification:April 12th, 2019 at 09:19 am
博客维护不易,如果你觉得我的文章有用,请随意赞赏