POJ - Counterfeit Dollar 题解

挺考智力的题目。

思路：

1 如果是假币，那么每次都必定引起天平的不平衡

2 如果天平平横，那么全部都肯定是真币

利用这个特性，利用hash表，就能写出很简洁的程序。

如果使用枚举，那么会（轻松？）过百行的代码的。

当然其实题目给出了条件：一定可以找出唯一的假币的。

如果没有这个条件，那么是不一定可以三次称，就能确定结果的。

#include 
  
   
#include 
   
     #include 
    
      using namespace std; class CounterfeitDollar { const static int ALPHA = 12; const static int TIMES = 3; string s1, s2, s3; public: CounterfeitDollar() { int n; cin>>n; while (n--) { int tbl[ALPHA][TIMES] = {0}; int balance[TIMES] = {0}; for (int i = 0; i < TIMES; i++) { cin>>s1>>s2>>s3; for (int j = 0; j < (int)s1.size(); j++) { tbl[s1[j] - 'A'][i] = -1; tbl[s2[j] - 'A'][i] = 1; } if ('e' == s3[0]) balance[i] = 0; else if ('d' == s3[0]) balance[i] = 1; else balance[i] = -1; } for (int i = 0; i < ALPHA; i++) { if (balance[0] == -tbl[i][0] && balance[1] == -tbl[i][1] && balance[2] == -tbl[i][2]) { cout<
     
      
 






      
更新一个新的解法：
      
1 如果是even，那么所有是真币，所以设置为10
      
2 如果硬币在轻的一方，那么--，如果在重的一方，那么++
      
3 最后找到差别最大的硬币，那么就为假币
      
4 如果假币为负数，那么就比真币轻， 如果为正，那么就比真币重。
      
 
      
这回是原创的程序的，感觉比前面的更加容易理解。
      
 
      
 
      
#include 
       
        
#include 
        
          #include 
         
           using namespace std; class CounterfeitDollar_2 { const static int ALPHA = 12; const static int TIMES = 3; string s1, s2, s3; public: CounterfeitDollar_2() { int n; cin>>n; while (n--) { int tbl[ALPHA] = {0}; int balance[TIMES] = {0}; for (int i = 0; i < TIMES; i++) { cin>>s1>>s2>>s3; if ('e' == s3[0]) { for (int i = 0; i < (int)s1.size(); i++) { tbl[s1[i] - 'A'] = 10; tbl[s2[i] - 'A'] = 10; } } else if ('d' == s3[0]) { for (int i = 0; i < (int)s1.size(); i++) { if (tbl[s1[i] - 'A'] != 10) tbl[s1[i] - 'A']--; if (tbl[s2[i] - 'A'] != 10) tbl[s2[i] - 'A']++; } } else { for (int i = 0; i < (int)s1.size(); i++) { if (tbl[s1[i] - 'A'] != 10) tbl[s1[i] - 'A']++; if (tbl[s2[i] - 'A'] != 10) tbl[s2[i] - 'A']--; } } } int id = 0, diff = 0; for (int i = 0; i < ALPHA; i++) { if (tbl[i] != 10 && diff < abs(tbl[i])) { diff = abs(tbl[i]); id = i; } } cout<