BestCoder36 1002.Gunner 解题报告

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5199

题目意思：给出鸟在树上的高度，以及射击到的高度，问每次射击能射中鸟的数量

　　用 vector 里面的 lower_bound() 函数求出大于等于某个 x 的下标，upper_bound() 求出大于某个 x 的下标，然后相减就是射中的数量了。vis[] 数组是防止再次击中相同高度的，明显是 0 嘛~~~。

　　因为是 huge input ，用到 get_int() 来加快输入（不过貌似没啥用 O.O）。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <vector>
 6 #include <algorithm>
 7 
 8 using namespace std;
 9 
10 const int maxn = 1e6 + 5;
11 int vis[maxn];
12 vector<int>::iterator p1, p2;
13 vector<int> h;
14 
15 inline int get_int()
16 {
17     char ch = getchar();
18     while (ch < '0' || ch > '9') {
19         ch = getchar();
20     }
21     int ret = 0;
22     while (ch >= '0' && ch <= '9') {
23         ret = ret * 10 + ch - '0';
24         ch = getchar();
25     }
26     return ret;
27 }
28 int main()
29 {
30     #ifndef ONLINE_JUDGE
31         freopen("in.txt", "r", stdin);
32     #endif // ONLINE_JUDGE
33 
34     int n, m, q, hi;
35     while (scanf("%d%d", &n, &m) != EOF) {
36         h.clear();
37         for (int i = 0; i < n; i++) {
38             hi = get_int();
39             h.push_back(hi);
40         }
41 
42         sort(h.begin(), h.end());
43 
44         memset(vis, 0, sizeof(vis));
45         for (int i = 0; i < m; i++) {
46             q = get_int();
47             p1 = lower_bound(h.begin(), h.end(), q);
48             p2 = upper_bound(h.begin(), h.end(), q);
49 
50             int pos1 = p1 - h.begin();
51             int pos2 = p2 - h.begin();
52             if (pos1 <= n && pos2 <= n && pos1 != pos2) {
53                 int t1 = h[pos1], t2 = h[pos2];
54                 if (t1 == q) {
55                     if (!vis[pos1]) {
56                         printf("%d
", pos2-pos1);
57                         vis[pos1] = 1;
58                     }
59                     else
60                         printf("0
");
61                 }
62             }
63             else
64                 printf("0
");
65         }
66     }
67     return 0;
68 }