转载请注明出处：優 YoU http://blog.csdn.net/lyy289065406/article/details/6661421
大致题意：
有一打（12枚）硬币，其中有且仅有1枚假币，11枚真币
用A~L作为各个硬币的代号
假币可能比真币略轻，也可能略重
现在利用天枰，根据Input输入的3次称量，找出假币，并输出假币是轻还是重。
解题思路：
模拟法要考虑的情况较繁琐，可利用简单的逻辑推理进行解题。
注意Input一行代表一次称量，每行有三个字符串，分别为
Left right status
代表该次称量时，天枰左盘放的硬币、天枰右盘放的硬币、天枰 右盘 的状态
共三种状态：
Up：右盘上升，说明右盘可能有轻假币，也可能左盘有重假币。
Down：右盘下降，说明右盘可能有重假币，也可能左盘有轻假币。
Even：右盘与左盘平衡，由于假币有且仅有1枚，则说明此时天枰两边的硬币全为真币。
注意题目的字眼：
1、 有且仅有1枚假币
2、 假币相对于真币的重量，可能轻可能重
3、 只称量3次，且称量3次恰好且必能找到假币
4、 每次称量时天枰两边的硬币数目一样
5、 选取哪些硬币称量由input决定
从3、4、5可知，由于无法知道每次选取称量的硬币，那么3次称量可能只选用了几个硬币，也可能仅有一两个硬币没有选上，那么用模拟法去记录每次用于称量的硬币的状态（真假，其中假币又有轻重之分）并推导没有被称量的硬币状态（或状态变化）是很困难的，虽然人很容易做到这点，但计算机却很难去“推导”，因为称量硬币的方法是无规律的且非常多。
那么只能通过适当转化问题后用另一种有效的方法去解决。
虽然称量硬币的方法是无规律且未知的，但是称量硬币后的结果却只有3个，up、down和 even。且当出现even时，天枰两边的硬币必然都为真币，假币必定在余下的硬币之间（这是因为假币有且只有一枚），那么我们就可以定义一个标记数组 zero[]去标记even时的真币，在以后的处理把他们排除在外。
而唯一难以处理的是up和down的状态，因为假币可能轻可能重，则这两种状态都无法得知究竟假币出现在天枰的哪边。
处理up和down状态方法：
当出现up或down状态时，天枰两边的所有硬币都应该被怀疑为假币（已标记必定为真币的硬币不必被怀疑）。
首先time[]记录每个硬币的被怀疑程度，time[i]=0表示该硬币i不被怀疑（即其可能为真币）。定义在up状态盘的硬币为“轻怀疑假币”，通过“--”操作加深其被怀疑为轻假币的程度，“负号”为轻假币的怀疑方向；在down状态盘的硬币为“重怀疑假币”，通过“++”操作加深其被怀疑为重假币的程度，“正号”为重假币的怀疑方向。
那么若一枚真币被怀疑为“轻假币”时，它就可能通过下次称量通过“++”操作取消嫌疑了。初始化所有硬币的怀疑程度均为0。
称量完毕后，找出被怀疑程度最大（注意取绝对值）的硬币，它就是假币。而当其怀疑方向为正时，则其为重假币。为负时，为轻假币。
1
//
Memory Time
2
//
252K 0MS
3
4
#include
<
iostream
>
5
#include
<
cmath
>
6
using
namespace
std;
7
8
int
main(
void
)
9
{
10
int
cases;
11
cin
>>
cases;
12
for
(
int
c
=
1
;c
<=
cases;c
++
)
13
{
14
char
left[
3
][
6
],right[
3
][
6
],status[
3
][
6
];
15
16
int
time[
'
L
'
+
1
]
=
{
0
};
//
标记各个字母被怀疑的次数
17
bool
zero[
'
L
'
+
1
]
=
{
false
};
//
标记绝对为真币的字母（令天枰平衡的所有字母）
18
19
for
(
int
k
=
0
;k
<
3
;k
++
)
20
cin
>>
left[k]
>>
right[k]
>>
status[k];
21
22
for
(
int
i
=
0
;i
<
3
;i
++
)
23
{
24
switch
(status[i][
0
])
//
检查天枰状态
25
{
26
case
'
u
'
:
//
up，天枰左重右轻
27
{
28
for
(
int
j
=
0
;left[i][j];j
++
)
29
{
30
time[ left[i][j] ]
++
;
//
左重
31
time[ right[i][j] ]
--
;
//
右轻
32
}
33
break
;
34
}
35
case
'
d
'
:
//
down，天枰左轻右重
36
{
37
for
(
int
j
=
0
;left[i][j];j
++
)
38
{
39
time[ left[i][j] ]
--
;
//
左轻
40
time[ right[i][j] ]
++
;
//
右重
41
}
42
break
;
43
}
44
case
'
e
'
:
//
down，天枰平衡
45
{
46
for
(
int
j
=
0
;left[i][j];j
++
)
47
{
48
zero[ left[i][j] ]
=
true
;
//
绝对真币
49
zero[ right[i][j] ]
=
true
;
//
绝对真币
50
}
51
break
;
52
}
53
}
54
}
55
56
int
max
=-
1
;
//
查找被怀疑程度最高的硬币（假币）
57
char
alpha;
58
for
(
int
j
=
'
A
'
;j
<=
'
L
'
;j
++
)
59
{
60
if
(zero[j])
//
绝对真币
61
continue
;
62
63
if
(max
<=
abs(time[j]))
64
{
65
max
=
abs(time[j]);
66
alpha
=
j;
67
}
68
}
69
70
cout
<<
alpha
<<
"
is the counterfeit coin and it is
"
;
71
if
(time[alpha]
>
0
)
72
cout
<<
"
heavy.
"
<<
endl;
73
else
74
cout
<<
"
light.
"
<<
endl;
75
}
76
return
0
;
77
}
