obsidian/笔记文件/2.笔记/供暖器.md

![[Pasted image 20220414231911.png]]

![[Pasted image 20220414231914.png]]

![[Pasted image 20220414231924.png]]

![[Pasted image 20220414231928.png]]

![[Pasted image 20220414231932.png]]

```cpp
class Solution {

 public int findRadius(int[] houses, int[] heaters) {

 int ans = 0;

 Arrays.sort(heaters);

 for (int house : houses) {

 int i = binarySearch(heaters, house);

 int j = i + 1;

 int leftDistance = i < 0 ? Integer.MAX_VALUE : house - heaters[i];

 int rightDistance = j >= heaters.length ? Integer.MAX_VALUE : heaters[j] - house;

 int curDistance = Math.min(leftDistance, rightDistance);

 ans = Math.max(ans, curDistance);

 }

 return ans;

 }

 public int binarySearch(int[] nums, int target) {

 int left = 0, right = nums.length - 1;

 if (nums[left] > target) {

 return -1;

 }

 while (left < right) {

 int mid = (right - left + 1) / 2 + left;

 if (nums[mid] > target) {

 right = mid - 1;

 } else {

 left = mid;

 }

 }

 return left;

 }

}
```

![[Pasted image 20220414231959.png]]

![[Pasted image 20220414232004.png]]

![[Pasted image 20220414232009.png]]

![[Pasted image 20220414232013.png]]

![[Pasted image 20220414232017.png]]

![[Pasted image 20220414232022.png]]

![[Pasted image 20220414232028.png]]

```cpp
class Solution {

public:

 int findRadius(vector<int>& houses, vector<int>& heaters) {

 sort(houses.begin(), houses.end());

 sort(heaters.begin(), heaters.end());

 int ans = 0;

 for (int i = 0, j = 0; i < houses.size(); i++) {

 int curDistance = abs(houses[i] - heaters[j]);

 while (j < heaters.size() - 1 && abs(houses[i] - heaters[j]) >= abs(houses[i] - heaters[j + 1])) {

 j++;

 curDistance = min(curDistance, abs(houses[i] - heaters[j]));

 }

 ans = max(ans, curDistance);

 }

 return ans;

 }

};
```

![[Pasted image 20220414232057.png]]