posts - 64, comments - 4, trackbacks - 0, articles - 0

poj2481cows(树状数组)

Posted on 2010-10-29 15:18 acronix 阅读(174) 评论(0)  编辑 收藏 引用 所属分类: hzshuai解题报告


题意:给每只cow的头尾坐标,求对于每只cow比他壮的cow,壮大的定义就是比他长就是比他壮。

分析:二维变一维,先按左边的坐标按 j 从大到小排列,然后是 i 左边的坐标从小到大,最后处理 i 就行了,跟stars一样。


cpp代码:

#include <cstdio>
#include 
<stdlib.h>
#include 
<algorithm>
#include 
<memory.h>
using namespace std;

int
 maxn;
int c[100010
];
struct
 Cow{
    
int
 s,e;
    
int
 id;
}cow[
100010
];
int cnt[100010
];
int
 n;

bool cmp(const Cow &a,const Cow &
b)
{
    
if (a.e ==
 b.e)
        
return a.s <
 b.s;
    
return a.e >
 b.e;
}

int Lowbit(int
 i)
{
    
return i&(-
i);
}

void up(int
 x)
{
    
int i =
 x;
    
while (i <=
 n)
    {
        c[i] 
+= 1
;
        i 
+=
 Lowbit(i);
    }
}

int down(int
 x)
{
    
int i = x , res = 0
;
    
while (i > 0
)
    {
        res 
+=
 c[i];
        i 
-=
 Lowbit(i);
    }
    
return
 res;
}


int
 main()
{
    
int
 i,x,y;
    
while (scanf("%d",&n) &&
 n)
    {
        maxn 
= 0
;
        memset(c,
0,sizeof
(c));
        
for (i = 1; i <= n ;i++
)
        {
            cnt[i] 
= 0
;
            scanf(
"%d %d",&x,&
y);
            cow[i].s 
= x+1 , cow[i].e = y+1
;
            cow[i].id 
=
 i;
            
if (maxn <
 cow[i].e)
                maxn 
=
 cow[i].e;
        }
        sort(cow
+1,cow+1+
n,cmp);

        
for (i = 1; i <= n;i++
)
        {
            
if (i > 1 && cow[i].s == cow[i-1].s && cow[i].e == cow[i-1
].e)
                cnt[cow[i].id] 
= cnt[cow[i-1
].id];
            
else cnt[cow[i].id] =
 down(cow[i].s);
            up(cow[i].s);
        }

        
for (i = 1; i <= n; i++
)
        {
            
if (i != 1
)
                printf(
" "
);
            printf(
"%d"
,cnt[i]);
        }
        printf(
"\n"
);

    }
    
return 0
;
}
 

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理