轉載請注明出處：優 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
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
