其实这道题只要找到了解题的切入口是很简单的 ：出现不等号必然是由假币引起的，所以假币在不等式两边出现的次数必然等于所输入的不等号的数。 通过tag 数组记录硬币是否在等号两边出现过，这样的被标记为1,遍历时跳过，没有被标记为 1 的可能是假币，再看数组num中记录的i硬币在不等式出现的次数是否等于不等号的次数
1
#include <stdio.h>
2#include <stdlib.h>
3#define MAX 1001
4#define OK 1
5
6int tag[MAX]; //将出现了等号的(即真币)排除 标记为1 遍历时跳过
7int num[MAX]; //记录下标为i的硬币在不等式的两边出现的次数
8
9int main ()
10
{
11
12 int coin[MAX]; //访问时下标的中介
13 int N, k, pi, count ;
14 char c;
15
16 while ( scanf ("%d%d", &N, &k) != EOF )
17
{
18 count = 0; //记录接下来的 k 次称量中有多少次出现了不等号
19
20 for ( int i = 0; i < k; i ++) // k 次的称量记录
21 {
22 scanf ("%d", &pi);
23 for (int j = 0; j < 2 * pi; j ++)
24 {
25 scanf ("%d", &coin[j]);
26
}
27
28 getchar ();
29
30 c = getchar ();
31
32 for (int i = 0; i < 2 * pi; i ++)
33 {
34 if (c == '=')
35 tag[coin[i]] = 1;
36
37 else if (c == '<')
38 {
39 count ++;
40 for (int j = 0; j < pi; j ++)
41 {
42 num[coin[j]]--;
43 }
44 for (int j = pi; j < 2 * pi; j++)
45 {
46 num[coin[j]]++;
47 }
48 }
49
50 else
51 {
52 count ++;
53 for (int j = 0; j < pi; j ++)
54 {
55 num[coin[j]]++;
56 }
57 for (int j = pi; j < 2 * pi; j++)
58 {
59 num[coin[j]]--;
60 }
61 }
62 }
63
64 }
65
66 int mark = 0;
67 int temp ;
68 for (int i = 1; i <= N; i ++)
69 {
70 if (tag[i] == 1) //表示为真币，不可能
71 continue;
72
73 if (num[i] == count || num[i] == -count) //如果硬币在不等式的两边出现的次数等于不等号数为假币
74 {
75 mark ++;
76 temp = i;
77 }
78 }
79
80 if (mark == 1) // 假币只有一个
81 {
82 printf ("%d\n", temp);
83 }
84
85 else
86 printf ("%d\n",0);
87
88 }
89
90 return 0;
91
}
92
posted on 2010-08-09 13:06
雪黛依梦 阅读(282)
评论(0) 编辑 收藏 引用