OpenJ_Bailian-2692 假币问题（思维题）

电玩女神 2022-01-26 15:09 167阅读 0赞

**Problem Description:**

赛利有12枚银币。其中有11枚真币和1枚假币。假币看起来和真币没有区别，但是重量不同。但赛利不知道假币比真币轻还是重。于是他向朋友借了一架天平。朋友希望赛利称三次就能找出假币并且确定假币是轻是重。例如:如果赛利用天平称两枚硬币，发现天平平衡，说明两枚都是真的。如果赛利用一枚真币与另一枚银币比较，发现它比真币轻或重，说明它是假币。经过精心安排每次的称量，赛利保证在称三次后确定假币。

**Input:**

第一行有一个数字n，表示有n组测试用例。   
对于每组测试用例：   
输入有三行，每行表示一次称量的结果。赛利事先将银币标号为A-L。每次称量的结果用三个以空格隔开的字符串表示：天平左边放置的硬币 天平右边放置的硬币 平衡状态。其中平衡状态用\`\`up'', \`\`down'', 或 \`\`even''表示, 分别为右端高、右端低和平衡。天平左右的硬币数总是相等的。

**Output:**

输出哪一个标号的银币是假币，并说明它比真币轻还是重(heavy or light)。

**Sample Input:**

1
    ABCD EFGH even 
    ABCI EFJK up 
    ABIJ EFGH even

**Sample Output:**

K is the counterfeit coin and it is light.

**思路：**

**开一个数组（下面代码中的dp数组）表示每个银币的状态，共有4中状态，分别用4个整数表示，未知状态用0表示，真币用2表示，轻的假币用-1表示，重的假币用1表示。**先将所有银币的状态都初始化为0，若两边相等的则两边的硬币都为真币，将两边银币的状态都置为2；如两边不等则两边必有一边存在假币，将轻的那边状态还是未知的银币的状态置为-1，将重的那边状态还是未知的银币的状态置为1。**判断银币为真币的情况有两种：一种是两边相等的情况；另一种是某个银币之前在轻的那边后来在重的那边，或者之前在重的那边后来在轻的那边，这样的银币也可以确定为真币。**最后状态为-1的输出并表明假币是轻的，状态为1的输出并表明假币是重的。

**上AC代码：**

#include <stdio.h>
    #include <string.h>
    int t;
    char a[7],b[7],res[5];
    int dp[12];
    int main()
    {
        scanf("%d",&t);
        while(t--)
        {
            int i,j;
            memset(dp,0,sizeof(dp));
            for(i=1;i<=3;i++)
            {
                scanf("%s %s %s",a,b,res);
                int len1=strlen(a);
                int len2=strlen(b);
                if(res[0]=='e')
                {
                    for(j=0;j<len1;j++)
                    {
                        dp[a[j]-'A']=2;
                    }
                    for(j=0;j<len2;j++)
                    {
                        dp[b[j]-'A']=2;
                    }
                }
                else if(res[0]=='u')
                {
                    for(j=0;j<len1;j++)
                    {
                        if(dp[a[j]-'A']!=2)
                        {
                            if(dp[a[j]-'A']==-1)
                            {
                                dp[a[j]-'A']=2;
                            }
                            else
                            {
                                dp[a[j]-'A']=1;
                            }
                        }
                    }
                    for(j=0;j<len2;j++)
                    {
                        if(dp[b[j]-'A']!=2)
                        {
                            if(dp[b[j]-'A']==1)
                            {
                                dp[b[j]-'A']=2;
                            }
                            else
                            {
                                dp[b[j]-'A']=-1;
                            }
                        }
                    }
                }
                else
                {
                    for(j=0;j<len1;j++)
                    {
                        if(dp[a[j]-'A']!=2)
                        {
                            if(dp[a[j]-'A']==1)
                            {
                                dp[a[j]-'A']=2;
                            }
                            else
                            {
                                dp[a[j]-'A']=-1;
                            }
                        }
                    }
                    for(j=0;j<len2;j++)
                    {
                        if(dp[b[j]-'A']!=2)
                        {
                            if(dp[b[j]-'A']==-1)
                            {
                                dp[b[j]-'A']=2;
                            }
                            else
                            {
                                dp[b[j]-'A']=1;
                            }
                        }
                    }
                }
            }
            for(i=0;i<12;i++)
            {
                if(dp[i]!=2&&dp[i]!=0)
                {
                    if(dp[i]==-1)
                    {
                        printf("%c is the counterfeit coin and it is light.\n",'A'+i);
                    }
                    else
                    {
                        printf("%c is the counterfeit coin and it is heavy.\n",'A'+i);
                    }
                    break;
                }
            }
        }
        return 0;
    }

**欢迎大家关注/订阅我的微信公众号Code Art Online，我会在我的公众号分享个人见闻，发现生活趣味；这里不仅有0和1，还有是诗和远方↓↓↓**

![20200227123106884.jpg][]

[20200227123106884.jpg]: /images/20220126/8b9832b77b4f4a4b9258dd4fc156cd2b.png