狗家曲折过经

lz "oding: 美国小白，一条街上有各种商店学校等等facility，你有一个facility list，选一个位置住，使得你到所有你需要的facility的距离和最小（超过一个位置选其中一个就成）。是面筋题，但是我没做过，当场先想了inverted index {facility -> [locations]}然后尝试所有位置，对每个facilit可以二分找到最小距离，这样时间O(mnlog(k))，空间O(mn)。后来发现可以再用一个map {facility -> last selected pos}存住上一次选的位置，这样就不用每次都二分了，时间变成O(mn" 这题是不是选中间的点?

douch 发表于 2019-4-28 14:46
lz "oding: 美国小白，一条街上有各种商店学校等等facility，你有一个facility list，选一个位置住，使得你 ...

不一定，结果和这几种facility的位置分布有关，只能线性搜过去。比方说你要的3种facility都有一家店在position k，那你肯定选择住在k，但是如果不都在一起而且有多家店，就只能每个位置都试试了。

deephama001 发表于 2019-4-28 23:07
不一定，结果和这几种facility的位置分布有关，只能线性搜过去。比方说你要的3种facility都有一家店在pos ...

明白了 谢谢lz

楼主你好，商店那个题是不是找中位数呢，如果奇数是中位数，偶数则是中间两个点的任意一点？

点赞。对了楼主我有个问题，巧克力怎么做成O(log(n)log(m))呢？我看了下其他讨论说是O(nlog(m))？是笔误吗？谢谢啦！
另外楼主我觉得你街道那个思路很好，这样的话还可以问如果要到几个地方的总距离最小，或者地图是二维（多维）的都可以高效解决。但是如果街道是让你只能走一次，甚至是parcing不断给后面的街区的情况的话就还是要用interval的解法啦。

LZ請問顯示器那題可以詳細解釋下解法嗎？有點不清楚