蛮力法的使用：-1083: False coin（1）

Beann

蛮力法的使用：-1083: False coin（1）

<div class="postbody"><div id="cnblogs_post_body">题目：http://acm.hzic.edu.cn/JudgeOnline/problem.php?id=1083
思路很简单 ：把所有的金币都试一遍。
Step 1： 依次假设I号金币是假的；
Step 2： 对称量的记录进行检测；如果假设与所有的记录都不矛盾，则有可能是假的 ；
Step 3： 如果有可能是假的金币只有一个，则输出他的编号；否则输出为0；
HINT  

• 不需要特殊的数据结构；
  
• 算法采用暴力搜索；
  

<div class="cnblogs_code" >View Code <div id="cnblogs_code_open_ae7c64f4-1929-41bc-a53a-9ebf1a97c5df" class="cnblogs_code_hide"> 1 #include<iostream> 2 using namespace std; 3 int jd(int,int *,char); 4 int main() 5 { 6     int num[100][1001]; 7     char s[1000];//输入内容 8     int n,i,j,t,k,no; 9     cin>>n>>k;10     for(i=0;i<k;i++)11     {12         cin>>num[0];13         for(j=1;j<=2*num[0];j++)14         {15             cin>>num[j];16         }    17         cin>>s;    18     }//以上为输入参数 19     for(i=1,t=0;i<=n;i++)//暴力搜索所有的情况 20     {21         for(j=0;j<k&&jd(i,num[j],s[j]);j++);22         //对所有情况的称量记录进行检测 23         if(j<k) continue;24         t++;//t保存嫌疑对象的个数 25         if(t>1)26         break;27         no=i; 28     } 29     if(t-1)30     cout<<0<<endl;31     else cout<<no<<endl;32     return 0;33 }34 35 int jd(int j,int *s,char c)36 {37     //函数判断假设j号金币是假的与称量结果是否矛盾38     //s是称量记录，其第一个元素是砝码个数39     //c是称量结果 40     int m,i,f;//f是判断测量是否含含有j号金币 41     m=s[0]<<1;//m是砝码个数乘以2，是指天平左右的总数 42     for(i=f=1;i<=m&&f;)43     if(s==j)44     f=0;45     else 46     ++i;47     //判断本次称量有没有j号金币。 48     if(!f&&c=='=' || f&&c!='=')49    return 0;//与假设矛盾 50    return 1;51 }