Posted on 2008-04-01 19:49
superman 閱讀(423)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ
This implement use the map in STL.
1 /* Accepted 1109 C++ 00:04.47 7992K */
2 #include <map>
3 #include <string>
4 #include <iostream>
5
6 using namespace std;
7
8 int main()
9 {
10 map <string, string> dict;
11
12 int n = 0; string s;
13 while(true)
14 {
15 getline(cin, s);
16 if(s == "")
17 break;
18
19 string a, b; int i;
20 for(i = 0; s[i] != ' '; i++)
21 a += s[i];
22 for(i = i + 1; i < s.size(); i++)
23 b += s[i];
24 dict[b] = a;
25 }
26
27 while(cin >> s)
28 {
29 if(dict.count(s))
30 cout << dict[s] << endl;
31 else
32 cout << "eh" << endl;
33 }
34
35 return 0;
36 }
37
This implement use quicksort and binay search.
1 /* Accepted 1109 C++ 00:04.34 6408K */
2 #include <string>
3 #include <stdlib.h>
4 #include <iostream>
5
6 using namespace std;
7
8 struct DICT { string en, mouse; } dict[100005];
9
10 int cmp(const void * a, const void * b)
11 {
12 DICT * c = (DICT *) a;
13 DICT * d = (DICT *) b;
14 return (c -> mouse < d -> mouse ? -1 : 1);
15 }
16
17 int main()
18 {
19 int n = 0; string s;
20 while(true)
21 {
22 getline(cin, s);
23 if(s == "")
24 break;
25 int i;
26 for(i = 0; s[i] != ' '; i++)
27 dict[n].en += s[i];
28 for(i++; i < s.size(); i++)
29 dict[n].mouse += s[i];
30 n++;
31 }
32
33 qsort(dict, n, sizeof(DICT), cmp);
34
35 while(cin >> s)
36 {
37 int l = 0, mid, r = n - 1, find = 0;
38 while(l <= r)
39 {
40 mid = (l + r) / 2;
41 if(dict[mid].mouse == s)
42 {
43 find = 1;
44 break;
45 }
46 if(dict[mid].mouse < s)
47 l = mid + 1;
48 else
49 r = mid - 1;
50 }
51 if(find)
52 cout << dict[mid].en << endl;
53 else
54 cout << "eh" << endl;
55 }
56
57 return 0;
58 }
59