hdu 5233 离散化

10^9的大数组显然开不了。所以也算比较裸的离散化了。。。

令pos[i].pp[j]表示从左到右第j个高度为i的树的位置　　（pp是个vector，范围0..now-1）

　pos[i].num表示有几个高度为i的树

　pos[i].now表示当前kill到第几个了（从0开始计数）

离散化模板get：

 1 int Bin(int key,int n,int X[])
 2 {
 3     int l = 0 , r = n - 1;
 4     while (l <= r)
 5     {
 6         int m = (l + r) >> 1;
 7         if (X[m] == key) return m;
 8         if (X[m] < key) l = m + 1;
 9         else r = m - 1;
10     }
11     return -1;
12 }
13 
14 int main()
15 {
16     //balabala
17 
18     
19     nnd=0;
20     for(int i=1; i<=N; i++)
21     {
22         scanf("%d",&h[i]);
23         X[nnd++]=h[i];            //先用数组X[1..m]存下这些数    
24     }
25     sort(X,X+nnd);                //然后对X从小到大排序
26     int m=1;
27     for(int i=1; i<nnd; i++)    //去重
28         if(X[i]!=X[i-1])    X[m++]=X[i];
29     sort(X,X+m);                //再排序一遍
30 
31     scanf("%d",&p);
32     int hs=Bin(p,m,X);            //hs就是p离散化之后的值
33 
34 
35     //balabala
36 }

AC Code：

 1 #include <iostream>
 2 #include <vector>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 struct abc
 9 {
10     vector<int> pp; //[0..num-1]
11     int num=0;
12     int now=0;
13 } pos[100010];
14 
15 int N,M,nnd;
16 int h[100010];
17 int Q;
18 int X[100010];
19 
20 int Bin(int key,int n,int X[])
21 {
22     int l = 0 , r = n - 1;
23     while (l <= r)
24     {
25         int m = (l + r) >> 1;
26         if (X[m] == key) return m;
27         if (X[m] < key) l = m + 1;
28         else r = m - 1;
29     }
30     return -1;
31 }
32 
33 int main()
34 {
35     while(cin>>N>>M)
36     {
37         memset(pos,0,sizeof(pos));
38         nnd=0;
39         for(int i=1; i<=N; i++)
40         {
41             scanf("%d",&h[i]);
42             X[nnd++]=h[i];
43         }
44         sort(X,X+nnd);
45         int m=1;
46         for(int i=1; i<nnd; i++)
47             if(X[i]!=X[i-1])    X[m++]=X[i];
48         sort(X,X+m);
49         //Bin(p,m,X);
50 
51         for(int i=1; i<=N; i++)
52         {
53             int tmp=Bin(h[i],m,X);
54             pos[tmp].num++;
55             pos[tmp].pp.push_back(i);
56         }
57 
58         for(int i=1; i<=M; i++)
59         {
60             scanf("%d",&Q);
61             int tmp=Bin(Q,m,X);
62             if(pos[tmp].num==0)
63                 printf("-1
");
64             else
65             {
66                 int tm=pos[tmp].now;
67                 pos[tmp].now++;
68                 pos[tmp].num--;
69                 int ans=pos[tmp].pp[tm];
70                 printf("%d
",ans);
71             }
72         }
73 
74     }
75 
76 
77     return 0;
78 }

View Code