【双指针】供暖器

改一下输入输出格式，输入n,m,表示n个房屋，m个供暖器，接下来输入n个整数和m个整数。输出一个整数，表示最小的供暖半径。

1 变量定义

1）a数组：存储房屋的位置
2）h数组：存储供暖器的位置
3）l变量：停留在a数组
4）r变量：停留在h数组
5）minn变量：定义为房屋到供暖器的最小距离
6） ans变量：定义为找到的最小半径

2 算法流程

l遍历a数组的元素，初始化minn=abs(a[l]-h[r]),如果r+1<=m && minn >= abs(a[l]-h[r+1]),则更新minn,r++。最好通过max(minn,ans)找到最终的ans。

3代码实现

#include<bits/stdc++.h>
using namespace std;
int l,r,n,m;
int a[100005],h[100005];
int main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++) cin>>h[i];sort(a+1,a+n+1);sort(h+1,h+m+1); l=1;r=1;int ans=0;for(int i=1;i<=n;i++){l=i;int minn=abs(h[r]-a[l]);while(r+1<=m&&abs(h[r+1]-a[l])<=minn){minn=abs(h[r+1]-a[l]);r++;} ans=max(ans,minn);} cout<<ans;return 0;
}