Skip to content

Latest commit

 

History

History

475.Heaters

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

475.Heaters

最佳的binary search方案是:遍历所有houses[i],记录其位置pos,在有序的heaters序列里找到第一个大于(等于)pos的迭代器元素it,判断*it和*(it-1)与pos的距离,较小值就是该house[i]的最小供暖半径。  

寻找it的方法用lower_bound函数。

auto it = lower_bound(heaters.begin(),heaters.end(),pos,cmp);

注意需要自定义比较函数cmp,return (a<b)。

特别注意当it==heaters.begin()或it==heaters.end()时的特例。说明houses[i]在所有heaters的一边,所以只需要计算单边的半径距离。