ApiDemos导入时No projects are found to import

题目:http://poj.org/problem?id=2828

题意:有n个人插队,给定插队的先后顺序和插在哪个位置还有每个人的val,求插队结束后队伍各位置的val。

线段树里比较简单的题目了,点的更新。。

思想是 从后向前插入,用num存储 每一段剩余的位置。

ApiDemos导入时No projects are found to import
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 using namespace std;
 7 const int maxn = 200000 + 10;
 8 int n, pos[maxn], val[maxn], ans[maxn];
 9 
10 struct node
11 {
12     int l, r, num;
13 }tr[4*maxn];
14 
15 void build(int t, int l, int r) //建树
16 {
17     tr[t].l = l; tr[t].r = r;
18     if(tr[t].l == tr[t].r)
19     {
20         tr[t].num = 1; //初始每一个剩余的位置为1
21         return;
22     }
23     int mid = (l+r)/2;
24     build(2*t, l, mid);
25     build(2*t+1, mid+1, r);
26     tr[t].num = tr[2*t].num + tr[2*t+1].num;
27 }
28 int query(int p, int t)
29 {
30     tr[t].num--;  //让对应的段的 剩余数减1
31     if(tr[t].l == tr[t].r)
32     return tr[t].l;
33     if(tr[2*t].num >= p) //如果左子树剩余数大于 要插入的位置就往左插入。
34     return query(p, 2*t);
35     else
36     return query(p - tr[2*t].num, 2*t+1);
37 }
38 int main()
39 {
40     int i, x;
41     while(~scanf("%d", &n))
42     {
43        memset(tr, 0, sizeof(tr));
44        build(1, 1, n);
45        for(i = 1; i <= n; i++)
46        scanf("%d%d", &pos[i], &val[i]);
47 
48        for(i = n; i >= 1; i--)
49        {
50            x = query(pos[i]+1, 1); //题目是从0开始的
51            ans[x] = val[i];  //让返回的位置 对应 val
52        }
53        for(i = 1; i < n; i++)
54        printf("%d ",ans[i]);
55        if(n >= 1)
56        printf("%d\n",ans[i]);
57     }
58     return 0;
59 }
ApiDemos导入时No projects are found to import

ApiDemos导入时No projects are found to import

上一篇:学习swing界面


下一篇:一张券APP的简介