本文共 1869 字，大约阅读时间需要 6 分钟。
题意：输入N个硬币，其中有且仅有一枚是假币，通过K次称重，求出哪个是假币，如果无法求出，输出0.
算法1：模拟
首先，对于假币，假设比真币重，那么不管如何组合，有假币的一侧一定重，而如果某枚硬币所在的结果有时重有时轻，则它一定是真币。
例，假设有4枚硬币，其中第2枚为假币，且比真币重，那么：
1 < 2
=> 此时结果：硬币1轻，硬币2重，说明二者一定有一枚是假币
1+2 > 3+4 => 此时结果：硬币1所在的集合重，而上一次判断的硬币1为轻，那么硬币1一定是真币。否则，假设硬币1为假币，那么本次的结果应该是1+2 < 3+4
定义：ans[i]=j，初始化为0，若j=INF说明i为真币，否则abs(j)为硬币i偏离真币的指数（即被怀疑为假币的次数），该值越大，越说明是假币
1.对于称重结果为等号的，两边一定是真币，将ans[i]置为INF
2.对于称重结果为小于号的，说明左侧的轻，右侧的重。对于左侧未判断出一定是真币的硬币i，如果ans[i]<=0，那么ans[i]--，如果ans[i]>0，说明i之前被判断过较重，如果i为假币，那么本次的结果一定是左侧的重右侧的轻，与已知结果矛盾，说明硬币i一定是真币，置ans[i]=INF。对于右侧未判断出一定是真币的硬币i，如果ans[i]>=0,那么ans[i]++，否则ans[i]=INF
3.如果称重结果为大于号，说明左侧的重，右侧的轻，处理结果类似步骤3
算法2：枚举，假设第i枚硬币是假币，然后验证K次称重结果，若符合则说明硬币i是假币，若有多个符合，说明无法判断，输出0
#include #include #include using namespace std;struct COIN{ int a[2010]; // 当前称的硬币 int k; // 每侧硬币的个数 char result; // 称重的结果 };COIN coins[110];const int INF = 99999; int ans[1010]; // 处理当前较轻的硬币 void light(int start, int end, int i){ for (int j=start; j = 0)? ans[coins[i].a[j]]++ : ans[coins[i].a[j]] = INF; } }}int main(){ int N,K; memset(ans,0,sizeof(ans)); // 输入 cin >> N >> K; for (int i=0; i > coins[i].k; for (int j=0; j<2*coins[i].k; j++) { cin >> coins[i].a[j]; } cin >> coins[i].result; } // 处理 for (int i=0; i <') { light(0,coins[i].k,i); heavy(coins[i].k, 2*coins[i].k, i); } else if (coins[i].result == '>') { heavy(0,coins[i].k,i); light(coins[i].k,2*coins[i].k,i); } } // 输出答案，绝对值最大的为假币，如果个数超过一个，则不能判断哪个是假币，即输出0 int max1,max2,falseCoin; max1 = max2 = -1; for (int i=1; i<=N; i++) { if (ans[i] != 99999) { if (abs(ans[i]) > max1) { max2 = max1; max1 = abs(ans[i]) ; falseCoin = i; } else if (abs(ans[i]) > max2) { max2 = abs(ans[i]); } } } (max1==max2)? cout << 0 << endl : cout << falseCoin << endl;}
转载地址：http://nrlbb.baihongyu.com/