题解 | Counterfeit Dollar（偷鸡思路）

思路：

已知只有一个假币而且给的样例一定有解，输入数据进行模拟，对每次称重按情况处理

1. even 则把参与称重的左右都标记为真；
2. up左边+1，右边-1（已经被标记为真的无需+-）
3. down左边-1，右边+1（已经被标记为真的无需+-）

因为假币唯一，最后比较出绝对值最大的即为假币，根据正负判断轻重

#include <cstdio>
#include <iostream>
#include <string>
#include <map>
#include <cmath>
#include <set>


using namespace std;

int main(){
    int N,M;
    string res[3];     //存称重结果
    string left[3],right[3];
    map<char,int> coin;
    map<char,int> tf;
    for(int i=0;i<3;i++){
        cin>>left[i]>>right[i]>>res[i];
    }
    for(int i=0;i<3;i++){       //把参与结果为even的coin标记为真
        if(res[i]=="even")
            for(int j=0;j<left[i].size();j++){
                tf[left[i][j]]=1;
                tf[right[i][j]]=1;
            }
        if(res[i]=="up")            //up左边+1 右边-1 已经标记为真的不参与+-
            for(int j=0;j<left[i].size();j++){
                if(tf[left[i][j]]!=1)
                    coin[left[i][j]]++;
                if(tf[right[i][j]]!=1)
                    coin[right[i][j]]--;
            }
        if(res[i]=="down")          //down左边-1 右边+1 已经标记为真的不参与+-
            for(int j=0;j<left[i].size();j++){
                if(tf[left[i][j]]!=1)
                    coin[left[i][j]]--;
                if(tf[right[i][j]]!=1)
                    coin[right[i][j]]++;
            }
    }
    map<char,int>::iterator it;
    int k=0;
    int zhong=1;      //记录轻重
    char faker;
    for(it=coin.begin();it!=coin.end();it++){
        if(tf[it->first]!=1 && abs(it->second)>k){      //比较出绝对值最大的即为假币
            k=abs(it->second);
            faker=it->first;
            if(it->second<0)
                zhong=-1;
        }
    }
    if(zhong==-1)
        cout<<faker<<" is the counterfeit coin and it is light.";
    else
        cout<<faker<<" is the counterfeit coin and it is heavy.";


    return 0;
}