本文主要是介绍PKU2352 Stars - 树状数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述：
按照y坐标升序，x坐标升序输入N个星星的坐标。若左下角有k个星星，定义星星的级别为k。输出级别为0~N-1的星星分别有多少。
分析：
输入顺序已排好序，那么只要依次统计星星i之前x坐标小于等于i.x的星星有多少，即是星星i的级别。
这样也就成了树状数组的模型。编码很简单，y坐标没用。
注意，x可能为0，处理时要将所有的x+1。（用树状数组的时候一定要注意这一点）还有就是x的范围不能事先确定，在Add的时候我直接加到了x取值范围的最大值。
- /*
- PKU2352 Stars
- */
- #include <stdio.h>
- #include <memory.h>
- #define clr(a) memset(a,0,sizeof(a))
- #define N 15005
- #define M 32005
- int n,m;
- int c[M]; //下标从1开始
- int level[N];
- void Add(int i,int t){
- while(i<M){
- c[i]+=t;
- i+=-i&i;
- }
- }
- int Sum(int i){
- int s=0;
- while(i>0){
- s+=c[i];
- i-=-i&i;
- }
- return s;
- }
- int main()
- {
- while(scanf("%d",&n)!=EOF){
- //init
- int i,j,k;
- clr(c); clr(level);
- m=0;
- //input
- for(k=0;k<n;k++){
- scanf("%d%*d",&i);
- level[Sum(++i)]++;
- Add(i,1);
- }
- //output
- for(i=0;i<n;i++){
- printf("%d/n",level[i]);
- }
- }
- return 0;
- }
这篇关于PKU2352 Stars - 树状数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
