【树状数组】POJ

【树状数组】POJ_2481 Cows

2024-01-30 04:58

文章标签 数组 poj 树状 cows 2481

本文主要是介绍【树状数组】POJ_2481 Cows，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出一些奶牛的坐标，其中如果有 $x [i] > x [j]$ 和 $y [i] > y [j]$ ，那么奶牛i就比奶牛j强，求出比每个奶牛强的奶牛的个数。

思路

这题和Stars差不多，只不过是它的y坐标不是按升序输入的，所以我们要给它们排序，以y坐标从大到小排序，y相同时以x从小到大排序，利用树状数组统计比当前奶牛强壮的的牛，并把当前牛加入树状数组。注意奶牛的x和y都相等的时候需要特殊处理。

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,tree[100001];
struct af{int x,y,s,ans;
}a[100001];
int lowbit(int x) {return x&-x;}
int cmp(af x,af y)
{return x.y>y.y||x.y==y.y&&x.x<y.x;
}
int cmp1(af x,af y) {return x.s<y.s;}
void add(int x)
{for (;x<=100001;x+=lowbit(x))tree[x]++;
}
int find(int x)
{int o=0;for (;x>0;x-=lowbit(x))o+=tree[x];return o;
}
int main()
{while(scanf("%d",&n),n){memset(tree,0,sizeof(tree));for (int i=1;i<=n;i++){scanf("%d%d",&a[i].x,&a[i].y);a[i].s=i;}sort(a+1,a+n+1,cmp);for (int i=1;i<=n;i++){if (i!=1&&a[i].x==a[i-1].x&&a[i].y==a[i-1].y) //判断当前奶牛的坐标和上一只奶牛坐标有相等的情况时{a[i].ans=a[i-1].ans;//答案一样add(a[i].x+1);//把当前奶牛x坐标放入树状数组里}else{a[i].ans=find(a[i].x+1);//求出答案add(a[i].x+1);//放入树状数组}}sort(a+1,a+n+1,cmp1);//按照编号排序回来for (int i=1;i<=n;i++)printf("%d ",a[i].ans);printf("\n");}
}