题目：有N个硬币，里面有一个硬币是坏的，现在称了M次（称两边放数量一样的硬币）并把结果作为输入，根据称的结果判断第几号硬币是坏的。
例如：输入如下
5 3 （5表示有5个硬币，3表示称了3次，下面依次是每次称的结果）
2 1 2 3 4 （2表示称的两边分别放两个硬币，分别是1、2和3、4）
< （1+2<3+4）
1 1 4 （1表示称的两边分别放一个硬币，分别是1和4）
= （1=4）
1 2 5 （1表示称的两边分别放一个硬币，分别是2和5）
= （2=5）
思路：
当两边一样重的时候，说明称量的硬币都是真的，对于这些硬币，我们直接做记号说明是真硬币。
当不一样重的时候，说明天平上肯定存在假硬币，但是我们不知道假硬币是在轻的一端还是重的一端。接下来这点很重要，天平不平衡了几次，假硬币肯定也出现了几次。所以对于不平衡时的称量，我们将称量的硬币出现的次数+1，注意，轻的一端和重的一端需要分开计数。最后我们比较天平不平衡的次数和每个硬币出现的次数，如果只有一个硬币称量的次数等于天平不平衡次数，说明该硬币就是假硬币。有多个时就无法判断出来。
#include<iostream> #include<algorithm> #include<string> #include<cstring> #include<cstdio> const int maxn=100005; using namespace std; int flag[maxn]; //记录硬币真假,1为真 int t[maxn]; //记录硬币原始数据 int w[maxn]; //记录硬币出现的次数，轻的和重的要分开记录，为正表示重的出现次数，负表示轻的出现次数 int main() { // freopen("E:\\ACM\\test.txt","r",stdin); int N,K,p; int total=0; //记录不等式出现出现次数 char c; cin>>N>>K; while(K--) { cin>>p; for(int i=0;i<2*p;i++) cin>>t[i]; cin>>c; if(c=='=') //为真 { for(int i=0;i<2*p;i++) flag[t[i]]=1; } else if(c=='<') //左轻右重 { ++total; for(int i=0;i<p;i++) w[t[i]]--; for(int i=p;i<2*p;i++) w[t[i]]++; } else if(c=='>') //左重右轻 { ++total; for(int i=0;i<p;i++) w[t[i]]++; for(int i=p;i<2*p;i++) w[t[i]]--; } } int count=0,pos=0; for(int i=1;i<=N;i++) { if(flag[i]==0&&(w[i]==total||w[i]==-total)) //找每次都出现的假币 { ++count; pos=i; } } if(count!=1) puts("0"); else cout<<pos<<endl; return 0; }
