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<