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

POJ2352树状数组

个人NO。1

一开始题意理解有错。

一星星左下边有N颗星星,那它的等级就是N。

一开始理解必须X,Y两个坐标都小于,后来根据样例看了一下只要左下方即可,X,Y坐标都小于等于即可,但不包括星星本身。

 

 
#include <iostream>   
#include <stdio.h>   
#include <string.h>   
using namespace std;  
int lowbit(int x)  
{  
    return x&-x;  
}  
int c[32005];  
int x[32005];  
int n;  
int ans[32005];  
int visit[32005];  
int a[32005];  
void add(int x,int y)//后面的所有的值得更新,不包括自身   
{  
    while(x<=32005)  
    {  
       c[x]+=y;  
       x+=lowbit(x);  
    }  
}  
int sum(int x)  
{  
    int ret=0;  
    while(x>0)  
    {  
        ret+=c[x];  
        x-=lowbit(x);  
    }  
    return ret;  
}  
int main()  
{  
    while(scanf("%d",&n)!=EOF)  
    {  
        memset(c,0,sizeof(c));  
        memset(x,0,sizeof(x));  
        memset(ans,0,sizeof(ans));  
        int x,y;  
        for(int i=1;i<=n;i++)  
        {  
            scanf("%d%d",&a[i],&y);  
            if(visit[a[i]+1]==0)  
            {  
                add(a[i]+2,1);  
                visit[a[i]+1]=1;  
            }  
            else   
            add(a[i]+1,1);//c[i]表示比i坐标小的个数   
            ans[sum(a[i]+1)]++;  
        }  
  
       for(int i=0;i<n;i++)  
           printf("%d\n",ans[i]);  
    }  
    return 0;  
}  

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int lowbit(int x)
{
    return x&-x;
}
int c[32005];
int x[32005];
int n;
int ans[32005];
int visit[32005];
int a[32005];
void add(int x,int y)//后面的所有的值得更新,不包括自身
{
    while(x<=32005)
    {
       c[x]+=y;
       x+=lowbit(x);
    }
}
int sum(int x)
{
    int ret=0;
    while(x>0)
    {
        ret+=c[x];
        x-=lowbit(x);
    }
    return ret;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(c,0,sizeof(c));
        memset(x,0,sizeof(x));
        memset(ans,0,sizeof(ans));
        int x,y;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&a[i],&y);
            if(visit[a[i]+1]==0)
            {
                add(a[i]+2,1);
                visit[a[i]+1]=1;
            }
            else 
            add(a[i]+1,1);//c[i]表示比i坐标小的个数
            ans[sum(a[i]+1)]++;
        }

       for(int i=0;i<n;i++)
           printf("%d\n",ans[i]);
    }
    return 0;
}


 

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