Zoj 3635 <树状数组+二分>

题意：

给出n表示geeks人数..也是位置总数..

给出a1 a2 .. ai .. an 表示第 i 个人想要坐从左往右第 ai 个空位..

给出m表示询问的个数..

给出m个数b1 b2 .. bi .. bn 表示询问第 bi 个人的位置..

思路：

如果模拟过程..

应该是先按要求排好位置..然后输出位置值..

排好位置的过程就用到了二分..

用树状数组表示当前位置前有多少个空位..

然后二分找出满足当前位置前面空位有 ai 个的位置..

Tips：

记得安排好第i个geeks的位置后要modify树状数组..

Code：

View Code

 1 #include <stdio.h>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 #define clr(x) memset(x, 0, sizeof(x))
 6 
 7 int n;       
 8 int c[100001]; 
 9 int lowbit(int x)
10 {
11    return (x)&(-x);
12 }
13 void modify(int pos,int x)
14 {
15     while(pos<=n)
16     {
17         c[pos]+=x;
18         pos+=lowbit(pos);
19     }
20 }
21 int getSum(int x)
22 {
23       int sum=0;
24       while(x>0)
25       {
26          sum+=c[x];
27          x-=lowbit(x);
28       }
29       return sum;
30 }
31 
32 int ans[50010];
33 int arr[50010];
34 int main()
35 {
36     int i, j, k;
37     int m, tmp;
38     while(scanf("%d", &n) != EOF)
39     {
40         clr(c);
41         clr(ans);
42         clr(arr);
43         for(i = 1; i <= n; ++i)
44         modify(i, 1);
45 
46         for(i = 1; i <= n; ++i){
47             scanf("%d", &tmp);
48             int r = n, l = 1, mid;
49             while(r > l)
50             {
51                 mid = (r+l)/2;
52                 if(getSum(mid) >= tmp) r = mid;
53                 else l = mid+1;
54             }
55             
56             arr[i] = r;
57             modify(r, -1);
58         }
59 
60 
61         scanf("%d", &m);
62         for(i = 0; i < m; ++i){
63             scanf("%d", &tmp);
64             ans[i] = arr[tmp];
65         }
66 
67         for(i = 0; i < m; ++i)
68         printf("%d%c", ans[i], i == m-1?'\n':' ');
69     }
70 
71     return 0;
72 }