Chinaunix

标题: 一道算法题 [打印本页]

作者: anselcat 时间: 2008-09-16 12:49
标题: 一道算法题
有n个水桶，组成一个环，相邻两个有水管连接，
水管中间有阀门，都关上。

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

作者: nicolas.shen 时间: 2008-09-16 13:19
阀门全部打开，让它们自己平衡

作者: ytl 时间: 2008-09-16 13:24
1. 计算平均值
2. 打开2边都不是平均值的阀门

不对。继续想

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

作者: 5毛党党员 时间: 2008-09-16 13:31
lz 是打开阀门最少，还是打开阀门次数最少？

作者: freearth 时间: 2008-09-16 13:32
可以同时打开多少个阀门？
比如，如果每次只能打开一个阀门，也就是说，在打开下一个阀门之前要关闭当前打开的；
还是不限制同时打开的阀门数？

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

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

作者: anselcat 时间: 2008-09-16 13:33
标题: 回复 #4 5毛党党员的帖子
应该是打开阀门个数最少吧

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

作者: ytl 时间: 2008-09-16 13:36

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

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

作者: insmile 时间: 2008-09-16 13:37

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

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

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

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

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

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

作者: cugb_cat 时间: 2008-09-16 13:40

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

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

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

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

作者: insmile 时间: 2008-09-16 13:41

原帖由 cugb_cat 于 2008-9-16 13:40 发表

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

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

这个是逐步平均了，应该不是最佳的

我觉得应该先计算各个桶的水深差，再进行调节

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

作者: epegasus 时间: 2008-09-16 13:43
这个题糊闹啊
不考虑物理效应，就是说2个桶之间开门，则瞬间平衡，那我开N-1个阀门就顺间OK了

作者: 5毛党党员 时间: 2008-09-16 13:44

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

因为是环所以没有第一个

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

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

求出最小的个数

作者: 5毛党党员 时间: 2008-09-16 13:45

原帖由 epegasus 于 2008-9-16 13:43 发表
这个题糊闹啊
不考虑物理效应，就是说2个桶之间开门，则瞬间平衡，那我开N-1个阀门就顺间OK了

关键是有可能比n-1小啊

作者: ytl 时间: 2008-09-16 13:45

原帖由 cugb_cat 于 2008-9-16 13:40 发表

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

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

那就可以统一处理，作为单独一个步骤除了增加复杂性之外没任何意义

作者: insmile 时间: 2008-09-16 13:46

原帖由 epegasus 于 2008-9-16 13:43 发表
这个题糊闹啊
不考虑物理效应，就是说2个桶之间开门，则瞬间平衡，那我开N-1个阀门就顺间OK了

就是，应该加一个条件，每次只能打开一个阀门，一个阀门可以打开多次

作者: cugb_cat 时间: 2008-09-16 13:46

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

因为是环所以没有第一个

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

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

我的意思是。。某一个。。任意一个。。

作者: benbenr 时间: 2008-09-16 13:46
平均值过后，多的肯定要流到小的地方。要流到，只有2个方向。每种距离都计算下，然后取小的。

作者: cugb_cat 时间: 2008-09-16 13:47

原帖由 epegasus 于 2008-9-16 13:43 发表
这个题糊闹啊
不考虑物理效应，就是说2个桶之间开门，则瞬间平衡，那我开N-1个阀门就顺间OK了

打开的阀门数最少，这是要求的。。

作者: cugb_cat 时间: 2008-09-16 13:48

原帖由 insmile 于 2008-9-16 13:46 发表

就是，应该加一个条件，每次只能打开一个阀门，一个阀门可以打开多次

如果考虑物理效应，那这个题就不该在本版讨论了。。
还是抽象成数学模型考虑吧。。

作者: benbenr 时间: 2008-09-16 13:49
要做到的竟可能在小范围能达到平均值就对了。

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

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

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

作者: ytl 时间: 2008-09-16 14:07

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

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

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

作者: benbenr 时间: 2008-09-16 14:13

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

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

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

作者: ytl 时间: 2008-09-16 14:15

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

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

同样是O(n^2)

作者: benbenr 时间: 2008-09-16 14:19
饿。。。汗。。。的确哦。倒了。

作者: xuezhg 时间: 2008-09-18 11:11

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

因为是环所以没有第一个

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

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

o(n^2)的做法

1，求出平均值

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

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

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

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

作者: jetvster 时间: 2008-09-19 12:19

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

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

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

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

作者: yoyocall 时间: 2008-09-19 22:11
标题: 回复 #13 5毛党党员的帖子
你是对的，不看你的解题思路连题目的意思都搞不明白

作者: pingtunao89 时间: 2008-09-20 06:50
提示: 作者被禁止或删除内容自动屏蔽

作者: pingtunao89 时间: 2008-09-20 07:48
提示: 作者被禁止或删除内容自动屏蔽

作者: pingtunao89 时间: 2008-09-20 08:03
提示: 作者被禁止或删除内容自动屏蔽

作者: xishagu39 时间: 2008-09-20 16:11
提示: 作者被禁止或删除内容自动屏蔽

作者: shc 时间: 2008-09-20 16:46
提示: 作者被禁止或删除内容自动屏蔽

作者: foxxx222 时间: 2008-09-20 16:48

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

o(n^2)的做法

1，求出平均值

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

4，以下一个桶 ...

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

作者: tanzhuomei71 时间: 2008-09-20 18:27
标题: 回复 #1 anselcat 的帖子
水桶有水，深度不一

作者: stone_pub 时间: 2008-09-21 13:56
1.找出平均
2.阀门两边 >均， < 均则开阀门开阀门后的两个视为一个

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

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

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

待续

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

作者: binaron 时间: 2008-09-21 23:56
续上
(1) 就是从a[0] 到 a[n-1] 的数组中寻找一个子数组a[j], a[j+1]……a[k] （0<=j<=k<=n-1)，且子数组的平均值等于整个数组的平均值。这一步我现在我只想到了O（n^2)的算法。大家帮忙想一下看看有没有O(n)的算法。
(2)就比较简单了，因为只是从一段进行分割，所以只要从一端加和就行，如果和=总的平局值*个数，就可以分割为一个自平衡区。

作者: towardWang 时间: 2008-09-22 13:17
先前的回帖有很大问题，仔细考虑之后，想法如下：
首先，这个问题的所有水桶形成的是一个环，是类似问题而水桶只是形成一个链表的问题的加强版，所以考虑将环转化成链表进行处理。而转化的关键就是找到一个断点，将环切断成链表。之后就可以对形成的链表进行遍历得到结果，这个遍历操作的时间复杂度为O(n)。
下面是全部的算法：
1。首先遍历整个环，将所有已经自平衡的水桶纪录在数组A[m]中。（可以证明，最佳的算法一定是以A[m]中的某个元素为断点的。）
2。遍历数组A[m],以每个元素为环的断点，做上述所说的对水桶链表进行平衡操作。
如以A[0]为断点，遍历当前形成的链表，纪录下为使链表得到平衡需要打开的水管个数（用于最后比较得出最佳结果），并在此过程中纪录下所有不需要打开的A[m]中的元素（因为这些元素在后面作为环的断点时会得到以A[0]作为环的断点一样的结果，所以现在纪录下来，就不用在遍历中对其进行操作。）

这样，对数组A[n]遍历完成后，会将A[m]分成k个组，每个组中包含若干个A[m]的元素和一个需要打开的水管个数count，这k个组中count最小的那个组就是要求的组。
总的时间复杂度为O(n*k)。n为水桶个数，k为对自平衡的水桶数组A[m]进行分组遍历的组数。

其中有个特殊情况，如果初始环没有自平衡水桶的话会出现问题。初步考虑，出现这种情况则对原始环间隔地插入一个自平衡的水桶将其变成符合上述条件的情况再进行处理。

[ 本帖最后由 towardWang 于 2008-9-22 13:20 编辑 ]

作者: binaron 时间: 2008-09-23 23:47
楼上的只是考虑了自平衡桶，没有考虑自平衡区，自平衡桶本身只是自平衡区的一个特例。

PS , 本题有误导之嫌，根本就没有O（n）算法，
在上面的论述中，我将题目分解成了两个部分，第一部分在o（n）范围内市不可能完成的，是可以用数学证明的。
第二部分本身就是o（n）的算法，就不用说了。

作者: towardWang 时间: 2008-09-24 08:51

原帖由 binaron 于 2008-9-23 23:47 发表
楼上的只是考虑了自平衡桶，没有考虑自平衡区，自平衡桶本身只是自平衡区的一个特例。

PS , 本题有误导之嫌，根本就没有O（n）算法，
在上面的论述中，我将题目分解成了两个部分，第一部分在o（n）范围内市 ...

两个相邻的平衡桶需要看成一个整体，新的大平衡桶。而且，经过调整后新平衡了某些桶，出现了新的相邻平衡桶也需要转变成一个新的大平衡桶。直到最后，全部桶转变成一个整体，则完成所有水桶的平衡。上面我所说的平衡桶形成的数组A[m]里面的元素应该是这样的一些大平衡桶，我没说清楚。

[ 本帖最后由 towardWang 于 2008-9-24 08:55 编辑 ]

作者: yixineryi 时间: 2008-09-24 13:07
标题: 指教
明天我再来，还没想清楚

作者: jeyochen 时间: 2008-09-24 20:38
这题出的有水平。值得思考

作者: jeanlove 时间: 2008-09-25 16:41

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

你的这个完全不对。
例如，我有5个水桶,编号1,2,3,4,5，而水量分别是1,2,3,4,5，5号和1号相连。然后按照你的意思，只有5号和1号之间的阀门打开了，变成了平均值。然后2，3，4的阀门都没开，得不到最后结果。

所以我认为应该不是一次运行就能解决问题，要运行多次，例如2和4之间的平衡就可以通过3达到。或者连通4,5,1,2也可以平衡这几个

算法分析，不用先分析N的情况，先分析一个很小的数量，就可以排出很多种谬误，你关推理N是推不出来的。

作者: pingtunao89 时间: 2008-09-26 10:32
提示: 作者被禁止或删除内容自动屏蔽

作者: pingtunao89 时间: 2008-09-26 10:45
提示: 作者被禁止或删除内容自动屏蔽

作者: houhulou 时间: 2008-09-26 12:24
binaron 的解法正确

作者: liugf 时间: 2008-09-26 17:47
标题: 回复 #1 anselcat 的帖子
you yisi

作者: xishagu39 时间: 2008-09-26 18:23
提示: 作者被禁止或删除内容自动屏蔽

作者: zhonghan 时间: 2008-09-26 22:35
提示: 作者被禁止或删除内容自动屏蔽

作者: nikia 时间: 2008-11-01 18:05
如果不考虑最大容量的话，可以这样设计：
1.计算整个数组的平均值；
2.从A[0]开始遍历数组，每找到一个大于平均值的数，记录该下标值，转到下步3；若无大于平均值的则完成开闸平衡；
3.从2步的下标开始，向两边找小于平均值的；正向（即数组下标为i+1）找到则方向控制为1，反向（即数组下标为n-i-1）为-1，退出按方向控制开始开闸，即最短的路径；回2，从2步记录的下标值开始继续遍历；

时间复杂度<O(n^2/4),最佳是o（N/2）.
说明：N为偶时为N，N为奇时N+1；

[ 本帖最后由 nikia 于 2008-11-2 19:02 编辑 ]

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)