忘记密码   免费注册 查看新帖 | 论坛精华区

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT HPC论坛 徽章 文库 沙龙 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
最近访问板块 发新帖
查看: 14048 | 回复: 53

一道算法题 [复制链接]

论坛徽章:
0
发表于 2008-09-16 12:49 |显示全部楼层
有n个水桶,组成一个环,相邻两个有水管连接,
水管中间有阀门,都关上。

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

论坛徽章:
0
发表于 2008-09-16 13:19 |显示全部楼层
阀门全部打开,让它们自己平衡

论坛徽章:
0
发表于 2008-09-16 13:24 |显示全部楼层
1. 计算平均值
2. 打开2边都不是平均值的阀门

不对。继续想

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

论坛徽章:
0
发表于 2008-09-16 13:31 |显示全部楼层
lz 是打开阀门最少,还是打开阀门次数最少?

论坛徽章:
0
发表于 2008-09-16 13:32 |显示全部楼层
可以同时打开多少个阀门?
比如,如果每次只能打开一个阀门,也就是说,在打开下一个阀门之前要关闭当前打开的;
还是不限制同时打开的阀门数?

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

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

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

回复 #4 5毛党党员 的帖子

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

论坛徽章:
0
发表于 2008-09-16 13:34 |显示全部楼层
1计算平均值;
2从第一个开始扫描,以阀门为考察对象,阀门有两个状态,开或关,如果某个阀门两边的水的高度一个高于平均值,一个低于平均值,则需要把该阀门打开,其他情况皆不打开。

论坛徽章:
0
发表于 2008-09-16 13:36 |显示全部楼层
原帖由 cugb_cat 于 2008-9-16 13:34 发表
1计算平均值;
2从第一个开始扫描,以阀门为考察对象,阀门有两个状态,开或关,如果某个阀门两边的水的高度一个高于平均值,一个低于平均值,则需要把该阀门打开,其他情况皆不打开。


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

论坛徽章:
0
发表于 2008-09-16 13:37 |显示全部楼层
原帖由 anselcat 于 2008-9-16 12:49 发表
有n个水桶,组成一个环,相邻两个有水管连接,
水管中间有阀门,都关上。

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


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

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


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

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

论坛徽章:
0
发表于 2008-09-16 13:40 |显示全部楼层
原帖由 ytl 于 2008-9-16 13:36 发表


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

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

这个解法我也不能确定是不是打开的阀门数最少,待证明。。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP