当前位置:编程学习 > C/C++ >>

POJ 2352 Stars


题目大意: 有n个星星, 现在分别给出它们的坐标(按y递增的顺序给出),每个星星有一个等级(该星星的等级是x坐标和y坐标都不大于该星的星星数),先要求出每个等级的星星有多少个

思路:用线段树或树状数组, 由于是按y递增的坐标给出的, 新加入一个点只需判断区间【1,x】多少个点, 并更新后面包含他区间的点的个数 
Ps:第一道树状数组, 资料链接资料1 资料2,顺便线段树练练手

code:树状数组
#include <stdio.h> 
int n = 0, c[32002]; 
int lowbit(int x) 

    return x&(-x); 

void add (int x) 

    while(x<=32002) 
    { 
        c[x]++; 
        x += lowbit(x); 
    } 

int sum(int x) 

    int s = 0; 
    while(x>0) 
    { 
        s += c[x]; 
        x -= lowbit(x); 
    } 
    return s; 

int main() 

    int i = 0, x = 0, y = 0, level[15002]; 
    while(scanf("%d",&n) != EOF) 
    { 
        memset(level, 0, sizeof(level)); 
        memset(c, 0, sizeof(level)); 
        for(i = 0; i<n; i++) 
        { 
            scanf("%d %d", &x, &y); 
            x++;//从1开始 
            level[sum(x)]++; 
            add(x); 
        } 
        for(i = 0; i<n; i++) 
            printf("%d\n",level[i]); 
    } 
    return 0; 

code:线段树
#include <stdio.h> 
#include <string.h> 
#define max 32002 
struct 

    int sum, l, r; 
}tree[4*max]; 
void build_tree(int l, int r, int p) 

    int m = (l+r)/2; 
    tree[p].sum = 0; 
    if(l == r) 
    { 
        tree[p].l = tree[p].r = l; 
        return ; 
    } 
    tree[p].l = l; tree[p].r = r; 
    build_tree(l, m, p*2); 
    build_tree(m+1, r, p*2+1); 

void add(int l, int r, int p) 

    int m = (tree[p].l+tree[p].r)/2; 
    if(tree[p].l == l && tree[p].r == r) 
    { 
        tree[p].sum++; 
        return ; 
    } 
    if(l>m) 
         add(l, r, 2*p+1); 
    else if(r<=m) 
         add(l, r, 2*p); 
    else 
    { 
         add(l, m, 2*p); 
         add(m+1, r, 2*p+1); 
    } 
    tree[p].sum = tree[p*2].sum+tree[p*2+1].sum; 

int query(int l, int r, int p) 

    int m = (tree[p].l+tree[p].r)/2; 
    if(tree[p].l == l && tree[p].r == r) 
        return tree[p].sum; 
    if(l>m) 
        return query(l, r, 2*p+1); 
    else if(r<=m) 
        return query(l, r, 2*p); 
    else 
        return query(l, m, 2*p)+query(m+1, r, 2*p+1); 
 

int main() 

    int i = 0, n = 0, x= 0, y = 0, lev[15002]; 
    while(scanf("%d", &n) !=  EOF) 
    { 
        memset(lev, 0, sizeof(lev)); 
        build_tree(0, max, 1); 
        for(i = 0; i<n; i++) 
        { 
            scanf("%d %d", &x, &y); 
            lev[query(0, x, 1)]++; 
            add(x, x, 1); 
        } 
        for(i = 0; i<n; i++) 
            printf("%d\n", lev[i]); 
    } 
    return 0; 

 

作者:ulquiorra0cifer
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,