免费注册 查看新帖 |

Chinaunix

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

一道算法题 [复制链接]

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

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

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


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


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

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

论坛徽章:
0
发表于 2008-09-16 13:43 |显示全部楼层
这个题糊闹啊
不考虑物理效应,就是说2个桶之间开门,则瞬间平衡,那我开N-1个阀门就顺间OK了

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

因为是环所以没有第一个

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

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

求出最小的个数

论坛徽章:
0
发表于 2008-09-16 13:45 |显示全部楼层
原帖由 epegasus 于 2008-9-16 13:43 发表
这个题糊闹啊
不考虑物理效应,就是说2个桶之间开门,则瞬间平衡,那我开N-1个阀门就顺间OK了

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

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

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

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


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

论坛徽章:
0
发表于 2008-09-16 13:46 |显示全部楼层
原帖由 epegasus 于 2008-9-16 13:43 发表
这个题糊闹啊
不考虑物理效应,就是说2个桶之间开门,则瞬间平衡,那我开N-1个阀门就顺间OK了


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

论坛徽章:
0
发表于 2008-09-16 13:46 |显示全部楼层
原帖由 5毛党党员 于 2008-9-16 13:44 发表

因为是环所以没有第一个

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

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

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

论坛徽章:
0
发表于 2008-09-16 13:46 |显示全部楼层
平均值过后,多的肯定要流到小的地方。要流到,只有2个方向。 每种距离都计算下, 然后取小的。

论坛徽章:
0
发表于 2008-09-16 13:47 |显示全部楼层
原帖由 epegasus 于 2008-9-16 13:43 发表
这个题糊闹啊
不考虑物理效应,就是说2个桶之间开门,则瞬间平衡,那我开N-1个阀门就顺间OK了

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

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


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

如果考虑物理效应,那这个题就不该在本版讨论了。。
还是抽象成数学模型考虑吧。。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP