写着写着写乱套了。下次一定要认真。
一开始没思路,看了中科院大佬的想法,才有了这个思路。
首先题目保证肯定会得到解,所以就放心的去写就行了。
设置三种状态:1(超重) 0(正常)-1(低重) 初始为2
1.当为even时,两组硬币都是正确的,设置为0
2.当为up时,左边重,则先判断左边有没有低重(==-1)的,如果低重就设成正常(0)
如果是初始值2,则设置为1;右边轻,判断右边有没有超重的,如果超重就设置成正常(0);其他的所有硬币都设置成正常(0)
3.当为down时,和情况2以样。
4.2和3两种情况当要处理的值为正常(0)时,continue。最后肯定有一种时非0的,1就是超重,-1就是低重 。
注意:如果硬币既超重又低重,说明硬币肯定是正常的。相当于反证法。可以举例论证一下。
#include<iostream> #include<string> #include<algorithm> using namespace std; const int maxn=12; int w[maxn]; string a,b,c,other; void init(){ for(int i=0;i<maxn;i++){ w[i]=2; } } int main(){ init(); while(cin>>a>>b>>c){ other=""; if(c=="even"){ for(int j=0;j<a.size();j++){ w[a[j]-'A']=w[b[j]-'A']=0; } }else if(c=="up"){ //左边重,右边轻 for(int j=0;j<a.size();j++){ if(w[a[j]-'A']==2)w[a[j]-'A']=1; //设置左 else if(w[a[j]-'A']==-1)w[a[j]-'A']=0; if(w[b[j]-'A']==2)w[b[j]-'A']=-1; //设置右 else if(w[b[j]-'A']==1)w[b[j]-'A']=0; } for(char s='A';s<='L';s++){ //其他都设置成正常的 if(a.find(s)==string::npos&&b.find(s)==string::npos){ w[s-'A']=0; } } }else if(c=="down"){ //右边重,左边轻 for(int j=0;j<a.size();j++){ if(w[a[j]-'A']==1)w[a[j]-'A']=0; else if(w[a[j]-'A']==2)w[a[j]-'A']=-1; if(w[b[j]-'A']==-1)w[b[j]-'A']=0; else if(w[b[j]-'A']==2)w[b[j]-'A']=1; } for(char s='A';s<='L';s++){ //其他都设置成正常的 if(a.find(s)==string::npos&&b.find(s)==string::npos){ w[s-'A']=0; } } } } for(int i=0;i<maxn;i++){ if(w[i]!=0){ if(w[i]==-1) printf("%c is the counterfeit coin and it is light.",i+'A'); else printf("%c is the counterfeit coin and it is heavy.",i+'A'); break; } } return 0; }