xindoo is
always here

poj 2352 Stars 树状数组


题目链接

Description

Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given
star. Astronomers want to know the distribution of the levels of the stars.………………

树状数组,简单题,我刚刚开始学的时候就a了,不多说什么了,直接贴代码。

#include<stdio.h>
#include<string.h>

int a[32002];
int level[15002];

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

void insert(int x)
{
	while(x<32002)
	{
		a[x]++;
		x += lowbit(x);
	}
}

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

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


打赏
未经允许不得转载:XINDOO » poj 2352 Stars 树状数组
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏