其實這道題只要找到了解題的切入口是很簡單的 ：出現(xiàn)不等號必然是由假幣引起的，所以假幣在不等式兩邊出現(xiàn)的次數(shù)必然等于所輸入的不等號的數(shù)。 通過tag 數(shù)組記錄硬幣是否在等號兩邊出現(xiàn)過，這樣的被標記為1,遍歷時跳過，沒有被標記為 1 的可能是假幣，再看數(shù)組num中記錄的i硬幣在不等式出現(xiàn)的次數(shù)是否等于不等號的次數(shù)
1
#include <stdio.h>
2#include <stdlib.h>
3#define MAX 1001
4#define OK 1
5
6int tag[MAX]; //將出現(xiàn)了等號的(即真幣)排除 標記為1 遍歷時跳過
7int num[MAX]; //記錄下標為i的硬幣在不等式的兩邊出現(xiàn)的次數(shù)
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 次稱量中有多少次出現(xiàn)了不等號
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) //如果硬幣在不等式的兩邊出現(xiàn)的次數(shù)等于不等號數(shù)為假幣
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
雪黛依夢 閱讀(291)
評論(0) 編輯 收藏 引用