一道算法题

benbenr

要做到的竟可能在小范围能达到平均值就对了 。

benbenr

是这样的，我认为是个环。流的方向只有2种，计算相邻的差值，直到最后就是平衡的，往2个方向计算，在段路径中能满足的就好。可以找平均值为起点。如果在搜索中达到一次平均值（或者说是差值==0）就要-1，少开一个阀门。

2个方向也就2N吧。不知道有没有问题。


感觉应该找最大的或者最小的容量的来做为起点。

ytl

原帖由 benbenr 于 2008-9-16 14:01 发表
是这样的，我认为是个环。流的方向只有2种，计算相邻的差值，直到最后就是平衡的，往2个方向计算，在段路径中能满足的就好。可以找平均值为起点。如果在搜索中达到一次平均值（或者说是差值==0）就要-1，少开一 ...

起点不好确定，只能从1到N逐个试探，从而总复杂度为O(n^2)
这个就是五毛那个算法

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

benbenr

原帖由 ytl 于 2008-9-16 14:07 发表


起点不好确定，只能从1到N逐个试探，从而总复杂度为O(n^2)
这个就是五毛那个算法

起点不用全部扫描的，要么扫小于平均值的，要么扫大于平均值的，这就够了。

ytl

原帖由 benbenr 于 2008-9-16 14:13 发表



起点不用全部扫描的，要么扫小于平均值的，要么扫大于平均值的，这就够了。

同样是O(n^2)

benbenr

饿。。。汗。。。的确哦。倒了。

xuezhg

原帖由 5毛党党员 于 2008-9-16 13:44 发表

因为是环所以没有第一个

我想的o(n^2)的做法

1，求出平均值
2，从任意一个桶开始，计算深度的总和，直到这个区域的深度总和 = 平均值 * 这个区域桶的个数
3，重复2，直到一次循环结束，结束后，记录区 ...

o(n^2)的做法

1，求出平均值

2，从任意一个桶开始，计算深度的总和，直到这个区域的深度总和 = 平均值 * 这个区域桶的个数，直到遍历了所有桶，记做一次循环结束，记录区域的个数

4，以下一个桶为起始桶，重复2
区域越多，需要打开的阀门越少；只有一个区域，需要全部打开

towardWang

1。计算平均值
2。遍历数组，除了等于平均值的水桶两边的水管外，其他水管全部打开，并且置对应的水管标志位1。
3。等打开的水桶的水平衡了之后，再遍历数组，考虑现在连续相邻的，且值等于平均值的水管，并且计算其中未打开的水管个数。由于这样的连续的水管可能有很多组，需要对每个组分别计算其中未打开的水管的个数，并取出它们的最大值为Max。则遍历完了之后，最少需要打开的水管个数为n-Max。时间复杂度为O(n)。

towardWang

1。计算平均值
2。遍历数组，除了等于平均值的水桶两边的水管外，其他水管全部打开，并且置对应的水管标志位1。
3。等打开的水桶的水平衡了之后，再遍历数组，考虑现在连续相邻的，且值等于平均值的水管，并且计算其中未打开的水管个数。由于这样的连续的水管可能有很多组，需要对每个组分别计算其中未打开的水管的个数，并取出它们的最大值为Max。则遍历完了之后，最少需要打开的水管个数为n-Max。时间复杂度O(n)。

jetvster

原帖由 ytl 于 2008-9-16 14:07 发表


起点不好确定，只能从1到N逐个试探，从而总复杂度为O(n^2)
这个就是五毛那个算法

这个问题的正解,但是这个的复杂度有点牵强.

要求最少的开阀个数除了这个遍历的方法好象没有更好的,我想不出来