g*********s
发帖数: 1782 | 1 有一 行 animal cages ，每个cage的动物的用水量为数组,有两个pipe给所有动物供水
，pipe给当前cage的cost 是 这个cage动物的用水量，给其他cage的动物供水的cost是
(distance to that cage)*那个cage动物的用水量， 求两个pipe供水的位置使cost最
小。
给当前cage的cost是0才对吧。 |
d*******l
发帖数: 338 | 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*********s
发帖数: 1782 | 3 what is the best solution so far?
【在 d*******l 的大作中提到】
: 这样更符合情理，但似乎对于O(n^3)和O(n^2)的方法并不会有影响
|
d*******l
发帖数: 338 | 4 好像能O(n)出来，那个thread里有人描述了
【在 g*********s 的大作中提到】
: what is the best solution so far?
|
f****4
发帖数: 1359 | 5 能给个url不？
谢谢
【在 d*******l 的大作中提到】
: 好像能O(n)出来，那个thread里有人描述了
|
d*******l
发帖数: 338 | |
g**********y
发帖数: 14569 | 7 我觉得出题的本意应该是：
当前的算x1,邻居算x2, ...
否则当前cost[i], 其余都是cost[k] * x * d, 这也太变态了。
【在 g*********s 的大作中提到】
: 有一 行 animal cages ，每个cage的动物的用水量为数组,有两个pipe给所有动物供水
: ，pipe给当前cage的cost 是 这个cage动物的用水量，给其他cage的动物供水的cost是
: (distance to that cage)*那个cage动物的用水量， 求两个pipe供水的位置使cost最
: 小。
: 给当前cage的cost是0才对吧。
|
g**e
发帖数: 6127 | 8 我也是这么理解的，所以开始一直没搞懂你们的解法
【在 g**********y 的大作中提到】
: 我觉得出题的本意应该是：
: 当前的算x1,邻居算x2, ...
: 否则当前cost[i], 其余都是cost[k] * x * d, 这也太变态了。
|
g***s
发帖数: 3811 | 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**e
发帖数: 6127 | 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.
|
a***x
发帖数: 26368 | 11 就这还华为呢
【在 g**e 的大作中提到】
: 现在懂了 :) 谢谢
: 今天被猎头搞的有点郁闷，脑袋不太清楚，唉
|
g*********s
发帖数: 1782 | 12 which solution?
【在 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.
|
