二分查找 BestCoder Round #42 1002 Gunner II

 1 /*
 2     题意：查询x的id，每次前排的树倒下
 3     使用lower_bound ()查找高度，f[i]记录第一棵高度为x树的位置，查询后+1(因为有序)
 4 */
 5 #include <cstdio>
 6 #include <algorithm>
 7 #include <cstring>
 8 using namespace std;
 9 
10 const int MAXN = 1e5 + 10;
11 const int INF = 0x3f3f3f3f;
12 struct A
13 {
14     int v, id;
15     bool operator < (const A &x) const
16     {
17         if (v == x.v)    return id < x.id;
18         return v < x.v;
19     }
20 }a[MAXN];
21 int h[MAXN], f[MAXN];
22 
23 inline int read(void)
24 {
25     int x = 0, f = 1;    char ch = getchar ();
26     while (ch < '0' || ch > '9')    {if (ch == '-') f = -1;    ch = getchar ();}
27     while (ch >='0' && ch <= '9')    {x = x * 10 + ch - '0';    ch = getchar ();}
28     return f * x;
29 }
30 
31 int main(void)        //HDOJ 5233 Gunner II
32 {
33     int n, q;
34     while (scanf ("%d%d", &n, &q) == 2)
35     {
36         for (int i=1; i<=n; ++i)    {a[i].v = read ();    a[i].id = i;}
37         sort (a+1, a+1+n);
38         for (int i=1; i<=n; ++i)
39         {
40             f[i] = i;    h[i] = a[i].v;
41         }
42         while (q--)
43         {
44             int x, p;    scanf ("%d", &x);
45             p = lower_bound (h+1, h+1+n, x) - h;
46             if (h[f[p]] != x)    {puts ("-1");    continue;}
47             printf ("%d
", a[f[p]].id);
48             f[p]++;
49         }
50     }
51 
52     return 0;
53 }
54 
55 /*
56 5 5
57 1 2 3 4 1
58 1 3 1 4 2
59 */
编译人生，运行世界！