POJ 1029 False coin

题意：

在一堆硬币中有一个假硬币，重量是重是轻不知道。每次称量多个硬币，并给出称量结果。判断依据题目给出的几次称量结果能否找出假硬币。

思路：

当两边一样重的时候，说明称量的硬币都是真的，对于这些硬币，我们直接做记号说明是真硬币。

当不一样重的时候，说明天平上肯定存在假硬币，但是我们不知道假硬币是在轻的一端还是重的一端。接下来这点很重要，天平不平衡了几次，假硬币肯定也出现了几次。所以对于不平衡时的称量，我们将称量的硬币出现的次数+1，注意，轻的一端和重的一端需要分开计数（也就是用两个数组来计数，因为我们不知道假硬币是重还是轻）。最后我们比较天平不平衡的次数和每个硬币出现的次数，如果只有一个硬币称量的次数等于天平不平衡次数，说明该硬币就是假硬币。有多个时就无法判断出来。

 1 #include<iostream> 
 2 #include<cstring>
 3 #include<string>
 4 using namespace std;
 5 
 6 int n, k;
 7 int pl[505],pr[505];
 8 int a[1005],b[1005];
 9 
10 int main()
11 {
12     while (cin >> n >> k)
13     {
14         int t;
15         int num = 0;
16         char c;
17         memset(a, 0, sizeof(a));
18         memset(b, 0, sizeof(b));
19         while (k--)
20         {
21             cin >> t;
22             for (int i = 0; i < t; i++)
23                 cin >> pl[i];
24             for (int i = 0; i < t; i++)
25                 cin >> pr[i];
26             cin >> c;
27             if (c == '=')
28             {
29                 for (int i = 0; i < t; i++)
30                 {
31                     a[pl[i]] = b[pl[i]] = -1;
32                     a[pr[i]] = b[pr[i]] = -1;
33                 }
34             }
35             else if (c == '<')
36             {
37                 num++;
38                 for (int i = 0; i < t; i++)
39                 {
40                     if (a[pl[i]] != -1)   a[pl[i]]++;
41                     if (a[pr[i]]!= -1)      b[pr[i]]++;
42                 }
43             }
44             else if (c == '>')
45             {
46                 num++;
47                 for (int i = 0; i < t; i++)
48                 {
49                     if (a[pl[i]] != -1)   b[pl[i]]++;
50                     if (a[pr[i]] != -1)      a[pr[i]]++;
51                 }
52             }
53         }
54         int ans, count=0;
55         for (int i = 1; i <= n; i++)
56         {
57             if (a[i] == num || b[i]==num)
58             {
59                 ans = i;
60                 count++;
61             }
62             if (count == 2)  break;
63         }
64         if (count!=1)  cout << "0" << endl;
65         else cout << ans << endl;
66     }
67 }