`
king_tt
  • 浏览: 2083198 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

poj 2352 Stars(树状数组 or 线段树)

 
阅读更多

链接:

http://poj.org/problem?id=2352


题目大意:

在坐标上有n个星星,如果某个星星坐标为(x, y), 它的左下位置为:(x0,y0),x0<=x 且y0<=y。如果左下位置有a个星星,就表示这个星星属于level x

按照y递增,如果y相同则x递增的顺序给出n个星星,求出所有level水平的数量。


分析与总结:

因为输入是按照按照y递增,如果y相同则x递增的顺序给出的, 所以,对于第i颗星星,它的level就是之前出现过的星星中,横坐标x小于等于i星横坐标的那些星星的总数量(前面的y一定比后面的y小)。

所以,需要找到一种数据结构来记录所有星星的x值,方便的求出所有值为0~x的星星总数量。

树状数组和线段树都是很适合处理这种问题。



代码:

1. 树状数组

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 32005;

int c[MAXN],level[MAXN],n;

int lowbit(int x){return x & (-x);}

// 求前n项的和
int sum(int n){
    int sum = 0;
    while(n > 0){
        sum += c[n];
        n -= lowbit(n);
    }
    return sum;
}
// 增加某个元素的大小
void add(int x){
    while(x <= MAXN){
        ++c[x];
        x += lowbit(x);
    }
}

int main(){
    int n,x,y;
    while(~scanf("%d",&n)){
        memset(level, 0, sizeof(level));
        memset(c, 0, sizeof(c));
        for(int i=0; i<n; ++i) {
            scanf("%d%d",&x,&y);
            ++x;
            level[sum(x)]++;
            add(x);
        }
        for(int i=0; i<n; ++i)
            printf("%d\n",level[i]);
    }
    return 0;
}

2. 线段树

#include<iostream>
#include<cstdio>
#include<cstring>
#define mid ((left+right)>>1)
#define lson rt<<1,left,mid
#define rson rt<<1|1,mid+1,right
using namespace std;

const int MAXN = 32005;

int sum[MAXN<<2],level[MAXN<<2];

void update(int rt,int left,int right,int data){
    ++sum[rt];
    if(left==right) return;
    if(data <= mid) update(lson,data);
    else update(rson,data);
}
int query(int rt,int left,int right,int l,int r){
    if(left==l && right==r) {
        return sum[rt];
    }
    int m = mid;
    if(r <= m) return query(lson,l,r);
    else if(l > m) return query(rson,l,r);
    else return query(lson,l,m)+query(rson,m+1,r);
}

int main(){
    int n,x,y;
    while(~scanf("%d",&n)){
        memset(sum, 0, sizeof(sum));
        memset(level, 0, sizeof(level));
        for(int i=0; i<n; ++i){
            scanf("%d%d",&x,&y);
            ++x;
            ++level[query(1,1,MAXN,1,x)];
            update(1,1,MAXN,x);
        }
        for(int i=0; i<n; ++i)
            printf("%d\n",level[i]);
    }
    return 0;
}


—— 生命的意义,在于赋予它意义士。

原创http://blog.csdn.net/shuangde800By D_Double (转载请标明)





分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics