首页 > 代码库 > poj 1029 false coin

poj 1029 false coin

2024-09-16 15:14:01   216人阅读

题目大意：就是一堆硬币中有一个假硬币，然后再给你几个天平的状态求出是否能找出哪个是假硬币并打印出编号。

主要思路：

可以使用穷举法。穷举1——n个硬币，分别判断是否是有问题的硬币（即假设该硬币有问题，是否与已知的天平判断结果一致），当然试探要分两种情况：重量轻了、重量重了。若全部试探完后发现：若个数为1，则说明有问题的硬币就是该硬币；否则说明有问题的硬币可能超过2个，则说明不能判断到底硬币是哪个。

主题思路清晰后，接下来就是如何判定是否与天平测试结果相一致。其实非常简单：

1）若为轻的情况。

  11） <  ，则该硬币必定在天平左边

  12） =  ，则该硬币比定既不在左边又不在右边

  13） >  ，则该硬币必定在天平右边

2）若为重的情况，稍微改动一下1）就可。

#include<iostream>
#include<stdio.h>

using namespace std;


int N,K,cnta[1000],cntb[1000],a[501],b[501],count,m;

int main(){

    char ch[3];
    while(scanf("%d%d",&N,&K)!=EOF){
        for(int i=0;i<1000;i++)
            cnta[i]=cntb[i]=0;   //初始化标志数组
        for(int i=0;i<K;i++){
            cin>>m;
            for(int j=0;j<m;j++){
                cin>>a[j];       //输入编号
            }
            for(int j=0;j<m;j++){
                cin>>b[j];
            }
            scanf("%s",&ch);
        if(ch[0]==‘=‘){
            for(int i=0;i<m;i++){
                cnta[a[i]]=cnta[b[i]]=cntb[a[i]]=cntb[b[i]]=-1;  //当两边相等时相应的编号硬币的标志数组全部-1标志这些硬币不会在以后的判断假币循环中
            }
        }
        else if(ch[0]==‘<‘){
            count++;
            for(int j=0;j<m;j++){
                if(cnta[a[j]]!=-1)
                    cnta[a[j]]++;
                if(cntb[b[j]]!=-1)
                    cntb[b[j]]++;
            }
        }
        else{
            count++;
            for(int j=0;j<m;j++){
                if(cntb[a[j]]!=-1)
                    cntb[a[j]]++;
                if(cnta[b[j]]!=-1)
                    cnta[b[j]]++; //将所有天平不等的情况下的硬币加入可疑硬币集合（即标志数组不为-1），并且可疑程度用标志数组的值来反映
            }
        }
        }
        int flag=0,ans=-1;
        for(int i=1;i<=N;i++){  //枚举开始
            if(cnta[i]!=-1)
            {

                flag++; //用flag来记录可疑硬币的个数
                ans=i;
            }
        }
        if(flag==1){
            cout<<ans<<endl; //为1即可输出
            continue;
        }
        flag=0;
        if(count!=0){
            for(int i=1;i<=N;i++){
                if(cnta[i]==count||cntb[i]==count)//如果标志数组的值和比较的次数相同，则可疑程度最大
                {

                    flag++;
                    ans=i;
                }
            }
            if(flag==1){
                cout<<ans<<endl;//如果只有一个硬币达到标准即为要求硬币
continue; } } printf("0\n"); } return 0; }

 

：

poj 1029 false coin


联系
我们