免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: anselcat

一道算法题 [复制链接]

论坛徽章:
0
发表于 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)就比较简单了,因为只是从一段进行分割,所以只要从一端加和就行,如果和=总的平局值*个数,就可以分割为一个自平衡区。

论坛徽章:
0
发表于 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 编辑 ]

论坛徽章:
0
发表于 2008-09-23 23:47 |显示全部楼层
楼上的只是考虑了自平衡桶,没有考虑自平衡区,自平衡桶本身只是自平衡区的一个特例。

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

论坛徽章:
0
发表于 2008-09-24 08:51 |显示全部楼层
原帖由 binaron 于 2008-9-23 23:47 发表
楼上的只是考虑了自平衡桶,没有考虑自平衡区,自平衡桶本身只是自平衡区的一个特例。

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


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

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

论坛徽章:
0
发表于 2008-09-24 13:07 |显示全部楼层

指教

明天我再来,还没想清楚

论坛徽章:
0
发表于 2008-09-24 20:38 |显示全部楼层
这题出的有水平。值得思考

论坛徽章:
0
发表于 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是推不出来的。

论坛徽章:
0
发表于 2008-09-26 10:32 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽

论坛徽章:
0
发表于 2008-09-26 10:45 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽

论坛徽章:
0
发表于 2008-09-26 12:24 |显示全部楼层
binaron 的解法正确
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP