共有回帖数 0 个
-
N 个球，有一个是坏的，坏球重量与好球不同（略轻/重于好球）。有一个天平，可以告知左右两边孰重孰轻，最小化最坏情况下称量次数，给出称量方案。
下面讨论该问题的一个扩展——如何通过已知信息（即之前称量结果，之前的称量结果可能不是最优的）选择下一步称量方案，最小化最坏情况下的称量次数。
根据已有信息把所有球分为4类：
0。肯定是好球
1。不可能比好球轻（不能确定是否为坏球）
2。不可能比好球重（不能确定是否为坏球）
3。不知道任何信息
每个球必定属于以上四类中的某一类。我们只需知道每一类的数目即可，具体编号无关紧要。
令 s[nh][nl][nu] 表示有 nh 个1类球，nl 个2类球，nu 个3类球，最坏情况下需要称量的次数。
枚举一边放置的各类型球数 lh(1类),ll(2类),lu(3类)
枚举另一边放置的各类型球数 rh(1类),rl(2类),ru(3类),re(0类)
如果两边都有0类球，那么我们可以在两边各移去一个。我们可以保证0类球只出现在一边，不妨设为 rh(1类),rl(2类),ru(3类) 一边。
s[nh][nl][nu] = max(
s[lh+lu][rl+ru][0]+1, #lh,ll,lu一边重于rh,rl,ru,re一边
s[rh+ru][ll+lu][0]+1, #lh,ll,lu一边轻于rh,rl,ru,re一边
s[nh-lh-rh][nl-ll-rl][nu-lu-ru]+1, #一样重
)
下面程序应用到了 C++0x 的 multi-declarator auto，该特性已经被 GCC 4.4 实现。
输入格式：
两个整数 n,m，分别表示球的数量和已经称量的次数
之后 m 行，每一行第一个数 t，之后是 t 个数 a[0...t-1]，代表天平左边各个球的编号，然后又是 t 个数 b[0...t-1]，代表天平右边各个球的编号，接着是一个字符 c
表示天平左右两边分别是 a[] 和 b[]，字符 c 表示称量结果, {E: 一样中，L: 左边重，R: 右边重}
输出结果为下一步的其中一种最优称量方案
比如输入
12 2
4 0 1 2 3 4 5 6 7 E
3 0 1 2 8 9 10 L
输出
8 - 9
表示有12个球，[0 1 2 3] 和 [4 5 6 7] 的称量结果是一样重
[0 1 2] 重于 [8 9 10]
易知坏球在 {8 9 10} 中，下一步比较 8 和 9 即可
楼主 2015-12-24 10:55 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
