Posted on 2010-10-29 15:18
acronix 阅读(406)
评论(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;
}