POJ1013 Counterfeit Dollar 解题报告
题目描述

http://poj.org/problem?id=1013

有12枚硬币(标记为A-L)，其中有1枚是假币，但不知道假币比真币更轻或更重。Sally借助于天平，设计出一种方案，可以恰好三次测量出谁是假币、比真币更轻或更重。要求你帮助Sally，根据她的测量数据，计算出谁是假币、比真币更轻还是更重。例如一组测量数据为：

ABCD EFGH even

ABCI EFJK up

ABIJ EFGH even

注意：天平左右的硬币数量总是相等的。

可以计算得出K是假币，且比真币更轻。

解决这道题的关键是抓住以下几个关键点：

（1）假币只有一个，因此在不平衡的测量中，假币一定会出现。记录硬币出现在不平衡测量中的次数，是判断假币的一个条件。但仅用这个条件是不够的，比如：

A B up

CD AB up

C D even

在这个例子中，A和B出现在不平衡测量中的次数相等，都是2，因此还需考虑第二点。

（2）假币在测量中表现是一致的，假如假币比真币更轻，那么它在不平衡测量中一定总在up的一边。所以，凡是在不平衡测量里，时而在up的一边，时而在down的一边，如上例中的A，则说明其对测量的失衡没有决定性作用，则一定是真币，应该将它标注出来。

（3）出现在平衡测量中的硬币全是真币，将它们标注出来。

定义COIN结构，如下：

struc COIN

{

bool appear;

int type;

int count;
};

其中，appear标记是否出现在三次测量中，因为并非所有硬币都参与测量；type表示硬币的类型，初始为UNDEFINED，确定为真币则为DOLLAR，若非真币出现在up一边则为LIGHT，否则为HEAVY；count表示硬币出现在不平衡测量中的次数。

算法分为三步：

Step 1：初始化COIN数组，为本轮计算做好准备。

Step 2：根据输入的测量数据，更新COIN数组。

Step 3：扫描COIN数组，找到假币，并将其信息打印出来。

// 1013.cpp// 2012-12-27 by btwsmile#include <stdio.h>#include <string.h>// define#define UNDEFINED -1#define LIGHT   0#define DOLLAR   1#define HEAVY   2#define N 12// struct COINstruct COIN{bool appear;int type;int count;};// functions// prepare - reset coin[]void prepare(COIN*);// update - update coin[]void update(COIN*, char*, char*, char*);// search - find Counterfeit in coin[]int search(COIN*);// entryint main(){COIN coin[N];char szLeft[10];char szRight[10];char szRelation[10];int n;scanf("%d", &n);for(int i = 0; i < n; ++i){prepare(coin);// scanf & updatefor(int j = 0; j < 3; ++j){scanf("%s %s %s", szLeft, szRight, szRelation);update(coin, szLeft, szRight, szRelation);}// find Counterfeitint iCounterfeit = search(coin);// printif(iCounterfeit > -1){printf("%c is the counterfeit coin and it is %s.\n", ('A'+iCounterfeit), ((coin[iCounterfeit].type == HEAVY) ? "heavy" : "light") );}}return 0;}// definitions// preparevoid prepare(COIN* coin){for(int i = 0; i < N; ++i){coin[i].appear = false;coin[i].type   = UNDEFINED;coin[i].count  = 0;}}// updatevoid update(COIN* coin, char* pszLeft, char* pszRight, char* pszRelation){int iSize = strlen(pszLeft);char* psz[2] = { pszLeft, pszRight };if( strcmp(pszRelation, "even") == 0 ) // "even"{for(int i = 0; i < iSize; ++i){for(int j = 0; j < 2; ++j){int index = psz[j][i] - 'A';coin[index].appear = true;coin[index].type = DOLLAR;}}}else // "up" or "down"{int iTypeLeft, iTypeRight;if( strcmp(pszRelation, "up") == 0 ){iTypeLeft = HEAVY;iTypeRight = LIGHT;}else{iTypeLeft = LIGHT;iTypeRight = HEAVY;}for(int i = 0; i < iSize; ++i){for(int j = 0; j < 2; ++j){int index = psz[j][i] - 'A';coin[index].appear = true;coin[index].count++;if(coin[index].type != DOLLAR){int iType = ((j>0) ? iTypeRight : iTypeLeft);if(coin[index].type == UNDEFINED)coin[index].type = iType;else if(coin[index].type != iType)coin[index].type = DOLLAR;}}}} // end else}// searchint search(COIN* coin){int iMaxCount = 0;int iCounterfeit = -1;for(int j = 0; j < N; ++j){if(coin[j].appear && coin[j].type != DOLLAR && coin[j].count > iMaxCount){iMaxCount = coin[j].count;iCounterfeit = j;}}return iCounterfeit;}