这个水管题出的不对吧？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

这个水管题出的不对吧？

这个水管题出的不对吧？# JobHunting - 待字闺中

g*s2011-04-14 07:04

1 楼

有一行 animal cages ，每个cage的动物的用水量为数组,有两个pipe给所有动物供水
，pipe给当前cage的cost 是这个cage动物的用水量，给其他cage的动物供水的cost是
(distance to that cage)*那个cage动物的用水量，求两个pipe供水的位置使cost最
小。
给当前cage的cost是0才对吧。

d*l2011-04-14 07:04

2 楼

这样更符合情理，但似乎对于O(n^3)和O(n^2)的方法并不会有影响

【在 g*********s 的大作中提到】

: 有一行 animal cages ，每个cage的动物的用水量为数组,有两个pipe给所有动物供水
: ，pipe给当前cage的cost 是这个cage动物的用水量，给其他cage的动物供水的cost是
: (distance to that cage)*那个cage动物的用水量，求两个pipe供水的位置使cost最
: 小。
: 给当前cage的cost是0才对吧。

g*s2011-04-14 07:04

3 楼

what is the best solution so far?

【在 d*******l 的大作中提到】

: 这样更符合情理，但似乎对于O(n^3)和O(n^2)的方法并不会有影响

d*l2011-04-14 07:04

4 楼

好像能O(n)出来，那个thread里有人描述了

【在 g*********s 的大作中提到】

: what is the best solution so far?

f*42011-04-14 07:04

5 楼

能给个url不？
谢谢

【在 d*******l 的大作中提到】

: 好像能O(n)出来，那个thread里有人描述了

d*l2011-04-14 07:04

6 楼

http://www.mitbbs.com/article_t/JobHunting/31849715.html

g*y2011-04-14 07:04

7 楼

我觉得出题的本意应该是：
当前的算x1,邻居算x2, ...
否则当前cost[i], 其余都是cost[k] * x * d, 这也太变态了。

【在 g*********s 的大作中提到】

g*e2011-04-14 07:04

8 楼

我也是这么理解的，所以开始一直没搞懂你们的解法

【在 g**********y 的大作中提到】

: 我觉得出题的本意应该是：
: 当前的算x1,邻居算x2, ...
: 否则当前cost[i], 其余都是cost[k] * x * d, 这也太变态了。

g*s2011-04-14 07:04

9 楼

他的解法通用啊。哪种理解都可以。
主要是sum(x)递增,sum(x,n)递减。所以sum(x) - sum(x+s-n)单调递增。再O(n)求得
sum(i)以
后，O(lgn)二分可以找到最小的x。
case 1: s=1的时候，就是所有都乘以距离（当前×0）
case 2: s=3就是当前×1，其它乘以距离。
如果当前的×1，距离邻居×2，这个跟所有乘以距离(case 1)等效。
case 1，当pipe=1的时候，就是weighed median.

【在 g**e 的大作中提到】

: 我也是这么理解的，所以开始一直没搞懂你们的解法

g*e2011-04-14 07:04

10 楼

现在懂了 :) 谢谢
今天被猎头搞的有点郁闷，脑袋不太清楚，唉

【在 g***s 的大作中提到】

: 他的解法通用啊。哪种理解都可以。
: 主要是sum(x)递增,sum(x,n)递减。所以sum(x) - sum(x+s-n)单调递增。再O(n)求得
: sum(i)以
: 后，O(lgn)二分可以找到最小的x。
: case 1: s=1的时候，就是所有都乘以距离（当前×0）
: case 2: s=3就是当前×1，其它乘以距离。
: 如果当前的×1，距离邻居×2，这个跟所有乘以距离(case 1)等效。
: case 1，当pipe=1的时候，就是weighed median.