新鲜狗狗店面，感觉是跪了啊。。。

wangyiduo999 发表于 2016-10-31 05:44
再准确点是mn^2的复杂度，m = 多少供暖站， n = 房子的个数

这dp费了大劲了……

Owenli20 发表于 2016-10-31 12:03
这dp费了大劲了……

lintcode原题是贴的hard难度也不是白贴的

zzgzzm 发表于 2016-10-31 08:53
哦，你说的对，最小m的上届应该和n有关（我的（房子最大间距+1）太松了，会浪费几次binary search）。
...

n = 1 不是把这个供暖站放在最远的两个房子的中点？m = 最大间距/2？

zzgzzm 发表于 2016-10-31 08:53
哦，你说的对，最小m的上届应该和n有关（我的（房子最大间距+1）太松了，会浪费几次binary search）。
...

我知道怎么回事了，我以为覆盖范围是半径的长度