题目
源地址:
http://poj.org/problem?id=1013
理解
总共有12枚银币,里面有一枚是假货。要求通过三次称量,找出那枚假币,并说出是重了还是轻了。题目中明确指出,三次称量必定能找出那枚假货,使得问题简化了很多。一开始的想法是完全模拟出来,但写到代码的时候感觉过于蛋疼,然后想能不能用一些由计算机来推导的方法。在具体的实现中,发现我很难把问题抽象成计算机可以处理的问题。在一份解题报告的启发下,想到了使用一个数值来度量每个银币可能为假币的可能性的方法。
代码
#include <iostream>
#include <stdlib.h>
using namespace std;
int main()
{
int n;
cin>>n;
while(n--)
{
char left[3][6],right[3][6],status[3][6];
int time['L'+1]={0};
bool zero['L'+1]={false};
for(int k=0;k<3;k++)
cin>>left[k]>>right[k]>>status[k];
for(int i=0;i<3;i++)
{
switch(status[i][0])
{
case 'u':
{
for(int j=0;left[i][j];j++)
{
time[ left[i][j] ]++;
time[ right[i][j] ]--;
}
break;
}
case 'd':
{
for(int j=0;left[i][j];j++)
{
time[ left[i][j] ]--;
time[ right[i][j] ]++;
}
break;
}
case 'e':
{
for(int j=0;left[i][j];j++)
{
zero[ left[i][j] ]=true;
zero[ right[i][j] ]=true;
}
break;
}
}
}
int max=-1;
char alpha;
for(int j='A';j<='L';j++)
{
if(zero[j])
continue;
if(max<=abs(time[j]))
{
max=abs(time[j]);
alpha=j;
}
}
cout<<alpha<<" is the counterfeit coin and it is ";
if(time[alpha]>0)
cout<<"heavy."<<endl;
else
cout<<"light."<<endl;
}
return 0;
}
更新日志
2014年07月10日 已AC(C++下通过,G++下WA),准备择日修复。