题目

思路

• 对于一个房子而言，要么是它左边最近的供暖器供暖，要么是它右边最近的供暖器供暖。
• 现在的问题就是如何在供暖器序列当中找到，特定房子的左边最近距离和右边最近距离
• 通过二分查找确定左边最近距离（找到供暖器序列当中小于等于cur_house_pos的右端点即可）

代码

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        // 对于所有的房屋而言，要么是前一个供暖器，要么是后一个供暖器供应
        // 那么，检查所有的房屋，可以得到最大值，就是需要的最小加热半径
        sort(houses.begin(), houses.end());
        sort(heaters.begin(), heaters.end());
        int num_houses = houses.size(), num_heaters = heaters.size();
        long long min_radius = 0;
        for (int i = 0; i < num_houses; ++i) {
            int cur_house_pos = houses[i];
            // 找到小于等于房屋位置的最右边的供暖器
            int left = 0, right = num_heaters - 1;
            while (left < right) {
                int mid = (left + right + 1) / 2;
                if (heaters[mid] <= cur_house_pos) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            // 小于等于房屋位置的供暖器可能不存在，heaters[right]可能是大于房屋位置的最左边数字
            // 因此需要加上abs
            long long dis_before = abs(cur_house_pos - heaters[right]);
            left = 0, right = num_heaters - 1;
            while (left < right) {
                int mid = (left + right) / 2;
                if (heaters[mid] >= cur_house_pos) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            long long dis_after = abs(heaters[left] - cur_house_pos);
            min_radius = max(min_radius, min(dis_before, dis_after));
        }
        return min_radius;
    }
};