注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj2352 stars 树状数组  

2011-04-08 17:54:21|  分类: 数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

找某颗星的左下角有几颗星。输出有多少颗星左下角拥有0颗星,有多少颗左下角拥有1颗星……一直到n-1 。
因为输入时是按y值是递增的,所以直接用x(x也是递增的)来构建树状数组,接下来其实就是统计x 前面有多少个比它少的数。
树状数组参考:http://zxj015.blog.163.com/blog/static/170613730201136105251115/

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
const int MAX = 32002;

int n,c[MAX],an[MAX];
int lowbit(int x){
    return x & (-x);
}
 
void add(int i, int w){
    int flag=i;
    while(i <= 32002){
        c[i] += w;
        i += lowbit(i);
    }
}
 
int sum(int i){
    int ans = 0,flag=i;
    while(i > 0){
        ans += c[i];
        i -= lowbit(i);
    }
    return ans;
}
 
int main()
{
    int i,j,num,x,y;

    while(scanf("%d",&n)!=EOF)
    {
      for(i=0;i<=32002;i++)
       {
           c[i]=0;
           an[i]=0;
       }
      for(i = 1; i <= n; i ++)
      {
                     scanf("%d%d",&x,&y);
                     x++; //注意不能为零
                     an[sum(x)]++;
                     add(x,1);
      }
     for(i=0;i<n;i++)
         printf("%d\n",an[i]);
   }
 
    return 0;
}
  评论这张
 
阅读(91)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018