Leetcode475.Heaters供暖器
2024-09-07 13:19:08
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
现在,给出位于一条水平线上的房屋和供暖器的位置,找到可以覆盖所有房屋的最小加热半径。
所以,你的输入将会是房屋和供暖器的位置。你将输出供暖器的最小加热半径。
说明:
- 给出的房屋和供暖器的数目是非负数且不会超过 25000。
- 给出的房屋和供暖器的位置均是非负数且不会超过10^9。
- 只要房屋位于供暖器的半径内(包括在边缘上),它就可以得到供暖。
- 所有供暖器都遵循你的半径标准,加热的半径也一样。
示例 1:
输入: [1,2,3],[2] 输出: 1 解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1,那么所有房屋就都能得到供暖。
示例 2:
输入: [1,2,3,4],[1,4] 输出: 1 解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1,这样所有房屋就都能得到供暖。
class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
sort(houses.begin(), houses.end());
sort(heaters.begin(), heaters.end());
int len1 = houses.size();
int len2 = heaters.size();
int res = 0;
int cnt = 0;//设定一个标记,标记为位置比目前第i个房屋小的供暖器,优化,不然会超时
for(int i = 0; i < len1; i++)
{
int temp = abs(houses[i] - heaters[cnt]);
for(int j = cnt + 1; j < len2; j++)
{
if(houses[i] == heaters[j])
{
temp = 0;
break;
}
else if(houses[i] < heaters[j])
{
temp = min(temp, heaters[j] - houses[i]);
}
else
{
temp = min(temp, houses[i] - heaters[j]);
cnt = j;
}
}
res = max(temp, res);
}
return res;
}
};
最新文章
- 用django创建一个项目
- batchInsert xml 配置 ibatis
- 将Linux文件清空的几种方法
- CocoaPods的版本升级
- oracle表连接——处理连接过程中另外一张表没有相关数据不显示问题
- AE+C# 向axPageLayoutControl1添加图例
- paip.提升性能---- 网站并发数的总结.txt
- JS判断浏览器类型以及版本号
- Ajax属性和函数以及 返回值之XML格式和文本格式(二)
- (九)boost库之文件处理filesystem
- CentOS 安装Node.js
- ACCP6.0 教程课件,可用
- crawler_google工作原理
- 计算理论:NFA转DFA的两种方法
- JAVA设计模式总结之23种设计模式
- Paho -物联网 MQTT C Cient的实现和详解
- 深度优先搜索(DFS)专题讲座PPT截图【需要原稿的请留言或私信】
- socket编程实例
- 高仿QQ头像截取
- nginx break-circus
热门文章
- Identifying a Blocking Query After the Issuing Session Becomes Idle
- neo4j安装APOC插件
- 在使用python语言的open函数时,提示错误OSError: [Errno 22] Invalid argument: ‘文件路径’
- 如果try中有return那么finally中不要有return不然不会执行try中的return
- 【BZOJ4407】于神之怒加强版
- fiddler抓包工具遇到的问题-------502报错
- 0821NOIP模拟测试赛后总结
- 转:linux下的c/c++开发
- HTML 项目符号
- 《DSP using MATLAB》Problem 7.35