475. 供暖器,很经典
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
现在，给出位于一条水平线上的房屋和供暖器的位置，找到可以覆盖所有房屋的最小加热半径。
所以，你的输入将会是房屋和供暖器的位置。你将输出供暖器的最小加热半径。
说明:
给出的房屋和供暖器的数目是非负数且不会超过 25000。给出的房屋和供暖器的位置均是非负数且不会超过10^9。只要房屋位于供暖器的半径内(包括在边缘上)，它就可以得到供暖。所有供暖器都遵循你的半径标准，加热的半径也一样。示例 1:
输入: [1,2,3],[2]输出: 1解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。示例 2:
输入: [1,2,3,4],[1,4]输出: 1解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。
第一种，错误的
intminRadius(vector<int>&houses, int&pos1, int&pos2) {
vector<int>::iteratorit1=find(houses.begin(), houses.end(), pos1);
vector<int>::iteratorit2=find(houses.begin(), houses.end(), pos2);
intradius1=*(it1+ (it2-it1) /2) -pos1,radius2=pos2-*(it1+ (it2-it1) /2);
//cout << " pos1 pos2 " << pos1 << " " << pos2 << " radius1 radius2 " << radius1 <<" "<< radius2 << endl;
returnradius1>radius2?radius1:radius2;
}
intfindRadius(vector<int>&houses, vector<int>&heaters) {
if (heaters.size() ==1) returnfabs(houses[0] -heaters[0]) >fabs(houses[houses.size() -1] -heaters[0]) ?fabs(houses[0] -heaters[0]) : fabs(houses[houses.size() -1] -heaters[0]);
sort(houses.begin(), houses.end());
sort(heaters.begin(), heaters.end());
intmaxRaius=0;
inttemp=fabs(houses[0] -heaters[0]);
maxRaius=maxRaius>temp?maxRaius : temp;
//cout << maxRaius << endl;
for (vector<int>::iteratorit=heaters.begin(); it!=heaters.end()-1;++it ) {
temp=minRadius(houses, *it, *(it+1));
maxRaius=maxRaius>temp?maxRaius : temp;
//cout << maxRaius << endl;
}
temp=fabs(houses[houses.size() -1] -heaters[heaters.size()-1]);
maxRaius=maxRaius>temp?maxRaius : temp;
//cout << maxRaius << endl;
returnmaxRaius;
}
我的想法是，比较每两个热水器中间地方，距离房子的两边距离分别为多少。当然了，热水器为1的时候，就看第一个房子和最后一个房子到热暑期的距离，谁比较大了。比如[1,2,3,4],[1,4]，其实最短距离为1，而不是2。
第二种，直接比较每个房屋前后热水器的距离
房屋左右侧的热水器，取距离小的那个，最终取的是所有房屋所需最大的那个半径。
intminRadius(vector<int>&heaters, int&target) {
if (target<heaters[0]) returnheaters[0] -target;
if (target>heaters[heaters.size() -1]) returntarget-heaters[heaters.size() -1];
intmid=0, low=0, high=heaters.size() -1;
while (low+1<high)
{
mid=low+ (high-low) /2;
if (target==heaters[mid]) return0;
elseif (target>heaters[mid]) {
low=mid;
}
else {
high=mid;
}
}//差值为1的时候就停止判断，所以需要再进行判断一下
if (heaters[low] ==target||heaters[high] ==target) return0;
else
{ returnmin(fabs(target-heaters[low]), fabs(target-heaters[high]));
}
}
intfindRadius(vector<int>&houses, vector<int>&heaters) {
if (heaters.size() ==1) returnmax(heaters[0] -houses[0], houses[houses.size() -1] -heaters[0]);
sort(heaters.begin(), heaters.end());//对热水器进行排序
inttemp,maxRaius=0;
for (vector<int>::iteratorit=houses.begin(); it!=houses.end();++it ) {
temp=minRadius(heaters, *it);
maxRaius=maxRaius>temp?maxRaius : temp;
//cout << maxRaius << endl;
}
//cout << maxRaius << endl;
returnmaxRaius;
}
