一道算法题

anselcat

有n个水桶，组成一个环，相邻两个有水管连接，
水管中间有阀门，都关上。

初始条件是：水桶有水，深度不一，保存在数组a[n]里面。
问：设计算法，针对具体的a[n]，使得打开阀门最少情况下，水桶深度相同。
时间复杂度<O(n^2),最佳是o（N）.

nicolas.shen

阀门全部打开，让它们自己平衡

ytl

1. 计算平均值
2. 打开2边都不是平均值的阀门

不对。继续想

[ 本帖最后由 ytl 于 2008-9-16 13:25 编辑 ]

5毛党党员

lz 是打开阀门最少，还是打开阀门次数最少？

freearth

可以同时打开多少个阀门？
比如，如果每次只能打开一个阀门，也就是说，在打开下一个阀门之前要关闭当前打开的；
还是不限制同时打开的阀门数？

原帖由 anselcat 于 2008-9-16 12:49 发表
有n个水桶，组成一个环，相邻两个有水管连接，
水管中间有阀门，都关上。

初始条件是：水桶有水，深度不一，保存在数组a[n]里面。
问：设计算法，针对具体的a[n]，使得打开阀门最少情况下，水桶深度相同 ...

anselcat

应该是打开阀门个数最少吧

cugb_cat

1计算平均值；
2从第一个开始扫描，以阀门为考察对象，阀门有两个状态，开或关，如果某个阀门两边的水的高度一个高于平均值，一个低于平均值，则需要把该阀门打开，其他情况皆不打开。

ytl

原帖由 cugb_cat 于 2008-9-16 13:34 发表
1计算平均值；
2从第一个开始扫描，以阀门为考察对象，阀门有两个状态，开或关，如果某个阀门两边的水的高度一个高于平均值，一个低于平均值，则需要把该阀门打开，其他情况皆不打开。

有时连接平均值的阀门也需要打开，以提供水流通路

insmile

原帖由 anselcat 于 2008-9-16 12:49 发表
有n个水桶，组成一个环，相邻两个有水管连接，
水管中间有阀门，都关上。

初始条件是：水桶有水，深度不一，保存在数组a[n]里面。
问：设计算法，针对具体的a[n]，使得打开阀门最少情况下，水桶深度相同 ...

“打开阀门最少”---------------------------------------------------

是一次打开多少个阀门使得水平均，还是打开阀门N次使得水平均，还是一个阀门可以打开多次 但是 是计算打开的阀门个数啊？


我觉得应该算次数，不是算个数

[ 本帖最后由 insmile 于 2008-9-16 13:38 编辑 ]

cugb_cat

原帖由 ytl 于 2008-9-16 13:36 发表


有时连接平均值的阀门也需要打开，以提供水流通路

这是最后要考虑的，当完成前2步后，还需要检查一遍，看哪些没有达到平均水平，然后找能把这些点都包含进去，并且距离最小的路径，然后把阀门打开就行了。。

这个解法我也不能确定是不是打开的阀门数最少，待证明。。