POJ1013-Counterfeit Dollar


转载请注明出处:優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 }
优质内容筛选与推荐>>
1、多线程总结
2、linux面试题参考答案
3、.NET陷阱之四:事件监听带来的问题与弱监听器
4、十四、EnterpriseFrameWork框架核心类库之简易ORM
5、目标检测--之RCNN


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号