〖面试题〗选择最佳地点使得移动代价最少？？

2017/9/10镜像同步28 回复

之前面试被问到一道题，总觉得很眼熟，但就是不会。。问题：n个仓库在一条线上，每个仓库货物数量不同，现在这n个仓库中选择一个最佳的位置，使得把其他仓库的货物都移到该位置的总代价最小？也就是数量×移动距离我只知道暴力做是o（n2），求问还有更好的方法吗？？？

订阅后，新回复会通过你的通知中心匿名送达。

9 条回复

dss886机器人#1 · 2017/9/10

这是个典型的动态规划吧，目测可以复杂度降到nlogn

NachtZ机器人#2 · 2017/9/10

用动态规划，从左扫一遍，得到一个仓库左边到这个仓库的距离和。从右扫一遍得到这个仓库右边的点到这个仓库的距离和。两边一加就取最小的一个得到结果了。复杂度是o(n)。

hxidkd机器人#3 · 2017/9/10

可以搜一下带权中位数

aaronma1993机器人#4 · 2017/9/10

是不是就相当于用一个数组存一遍前缀和，然后再存一遍后缀和，然后就可以on求最小了吧【在 NachtZ 的大作中提到: 】 : 用动态规划，从左扫一遍，得到一个仓库左边到这个仓库的距离和。从右扫一遍得到这个仓库右边的点到这个仓库的距离和。两边一加就取最小的一个得到结果了。复杂度是o(n)。

aaronma1993机器人#5 · 2017/9/10

嗯嗯【在 hxidkd 的大作中提到: 】 : 可以搜一下带权中位数

TvT666机器人#6 · 2017/9/10

可以多解释一下么？on是怎么做到的。每次数组面存的是距离还是货物数量？【在 aaronma1993 的大作中提到: 】 : 是不是就相当于用一个数组存一遍前缀和，然后再存一遍后缀和，然后就可以on求最小了吧

aaronma1993机器人#7 · 2017/9/11

光是距离貌似不够哎，因为代价是距离x货物数量，好像不能直接由前一个得到后一个【在 NachtZ 的大作中提到: 】 : 用动态规划，从左扫一遍，得到一个仓库左边到这个仓库的距离和。从右扫一遍得到这个仓库右边的点到这个仓库的距离和。两边一加就取最小的一个得到结果了。复杂度是o(n)。

a940100079机器人#8 · 2017/9/11

直接撸代码直接用距离差了货物数量了所以就像你说的从左到右一遍前缀和从右向左一遍前缀和然后求min就可以啦

TvT666机器人#9 · 2017/9/11

goods和距离之间不应该是相乘再求和？【在 a940100079 的大作中提到: 】 : 直接撸代码 : 直接用距离差了货物数量了 : 所以就像你说的从左到右一遍前缀和 : ...................