一道算法题

yoyocall

你是对的，不看你的解题思路连题目的意思都搞不明白

foxxx222

原帖由 xuezhg 于 2008-9-18 11:11 发表



o(n^2)的做法

1，求出平均值

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

4，以下一个桶 ...

第二步加一条，如果找到深度=平均值的桶，则从这些桶开始。

tanzhuomei71

水桶有水，深度不一

stone_pub

1.找出平均
2.阀门两边 >均， < 均 则开阀门 开阀门后 的两个 视为一个

然后继续判断， 剩余所有 阀门 两边 都平（即都为均值 ）结束

binaron

此题的主要目的是求打开阀门最少的情况下使各桶内的水达到平衡，
首先分析一下，什么情况下可以打开的阀门最少，还能使各桶内的水达到平衡？下面一步步分析，打开桶最少还能使水平衡的条件。
1. 将所有桶都连起来，会达到平衡，这需要打开n-1个阀门；
2. 如果有一个桶的水等于 所有桶的水的平均值，不连接这个桶也可以使水达到平衡， 这需要打开n-2个阀门；
3. 如果 m个相连的桶平均值等于所有桶的平均值，那么把他们相连，其他桶相连，而两组桶之间不连也可以使水达到平衡。这里我们把相连的，水的平均值等于所有桶的平均值的m个桶称作：自平衡区；
4. 根据定义，值等于所有桶平均值的单个桶也平衡区， 所有桶组成的集体也是一个自平衡区
5. 从上面可以看出，所谓找打开最少的阀门也能平衡的条件，就是在这n个桶中找尽可能多的自平衡区，把自平衡区内相连，而去之间不用相连就可以达到平衡；

下面讨论一下可能的解法，即分割尽可能多的自平衡区的方法：
1. 在所有桶组成的环还未被分割的时候，分割出一个自平衡区，剩下的也是一个自平衡去；
2. 在第一次分割后，环已经不存在了，所以如果从一个自平衡区分割出去一个自平衡区，剩下的可能就不是一个自平衡区，而是两个不连续的碎片； 但是如果限定，第一次分割完成后，再分割的时候，只能从两端分割，那么分割出去一个自平衡区后，剩下的还是一个自平衡区
3. 所以问题转化为以下两步：
   （1）寻找第一个全集自平衡区之外的自平衡区，将全集分割成两个自平衡区
   （2）对这两个平衡区进行分割，从两端进行（也即是从一端进行，这一端分出区了，当然也就剩下那一端了）

待续

[ 本帖最后由 binaron 于 2008-9-21 18:15 编辑 ]