L475 供暖器

数组

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
现在，给出位于一条水平线上的房屋和供暖器的位置，找到可以覆盖所有房屋的最小加热半径。
所以，你的输入将会是房屋和供暖器的位置。你将输出供暖器的最小加热半径。
说明:
给出的房屋和供暖器的数目是非负数且不会超过 25000。
给出的房屋和供暖器的位置均是非负数且不会超过10^9。
只要房屋位于供暖器的半径内(包括在边缘上)，它就可以得到供暖。
所有供暖器都遵循你的半径标准，加热的半径也一样。

解：
关键是找到House两侧的heaters，可以顺序找，也可以二分找。

class Solution {
public:
     int findRadius(vector<int>& houses, vector<int>& heaters) {
           int res=0;
           //sort two array
           //sort(houses.begin(),houses.end());
           sort(heaters.begin(),heaters.end());
           for(int house:houses){
               auto pos = lower_bound(heaters.begin(),heaters.end(),house);
               int dist1 = (pos==heaters.end())?INT_MAX: *pos - house;
               int dist2 = (pos==heaters.begin())?INT_MAX:house - *(--pos);
               res = max(res,min(dist1,dist2));
           }
           return res;
       }
     // 用lower_bound来代替二分查找
     int findRadius(vector<int>& houses, vector<int>& heaters) {
           int n=heaters.size(),j=0,res=0;
           //sort two array
           sort(houses.begin(),houses.end());
           sort(heaters.begin(),heaters.end());
           for(int i=0;i<houses.size();i++){
               int left=0,right=n;
               while(left<right){
                   int mid = left + (right-left)/2;
                   if(heaters[mid]<houses[i]) left=mid+1;
                   else right=mid;
               }
               int dist1 = (right==n)?INT_MAX:heaters[right]-houses[i];
               int dist2 = (right==0)?INT_MAX:houses[i]-heaters[right-1];
               res = max(res,min(dist1,dist2));
           }
           return res;
       }
     //再用二分查找缩短时间
      int findRadius(vector<int>& houses, vector<int>& heaters) {
          int n=heaters.size(),j=0,res=0;
          //sort two array
          sort(houses.begin(),houses.end());
          sort(heaters.begin(),heaters.end());
          for(int i=0;i<houses.size();i++){
              int cur = houses[i];
              // find close heater，left house right, if left>=right继续找
              while(j<n-1 && abs(heaters[j+1]-cur) <= abs(heaters[j]-cur) )
                  ++j;
              res = max(res, abs(heaters[j]-cur));
          }
          return res;
      }
      //-------------------//
      ////多余用radius变量，直接用两个abs比较完了，和res选大的就挺好的。     
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        int res=0;
        int radius=0;
        int left=0,right=0;
        if(heaters.size() ==1){
            left = abs(houses.front()-heaters[0]);
            right = abs(houses.back()-heaters[0]);
            res = left>right?left:right;
            return res;
        } 
        sort(houses.begin(),houses.end());
        sort(heaters.begin(),heaters.end());
        if(heaters[0] > houses.back()) return (heaters[0] -houses.front());
        if(heaters.back() < houses[0]) return (heaters.back() -houses.back());
        heaters.push_back(INT_MAX);
        int max;
        int maxj=0;
        for(int i=0;i<houses.size();i++){
            max = INT_MAX;
            for(int j=maxj;j<heaters.size();j++){
                left =abs(houses[i] -heaters[j]);
                if(j==heaters.size()-1) left = right;
                else right = abs(heaters[j+1]-houses[i]);
                radius = left<right?left:right;
                if(radius <= max) {
                    max = radius;
                    maxj = j;
                }
                else j=heaters.size();
            }
            if(max > res) res=max;
        }
        return res;
    }
};