17 Cows POJ - 2481

Cows POJ - 2481

1 题意

  给出n个牛的取食范围 [Si,Ei],若Si<= Sj,Ej<=Ei,Ei-Si > Ej-Sj;则称i牛大于j牛,问对于每一个牛,有多少个牛比它大

2 分析

对于n个牛,先按照右端点进行排序,排序之后用树状数组插入和查询,只需要比较左端点,左端点比i牛小,说明比i牛大(相等的除外)

4 参考代码

 const int LEN = 1e5+100; int tree[LEN]; struct Cow { int s,e; int ID; }; bool operator<(const Cow &a,const Cow &b) { if(a.e!=b.e) return a.e>b.e; return a.s < b.s; } //int sum_of_len[LEN]; Cow cow[LEN]; int num[LEN]; int maxn = 0; void Update(int x) { while(x<=maxn+1) { tree[x]++; x += lowbit(x); } } int Query(int x) { int sum = 0; while(x>0) { sum += tree[x]; x -= lowbit(x); } return sum; } int main() { // freopen("D:\\in.txt","r",stdin); int N; while(cin>>N&&N) { maxn = 0; memset(tree,0,sizeof(tree)); memset(num,0,sizeof(num)); for(int i = 1; i <= N; ++i) { scanf("%d %d",&cow[i].s,&cow[i].e); cow[i].ID = i; maxn = max(cow[i].s,maxn); } sort(cow+1,cow+N+1); for(int i = 1; i <= N; ++i) { if (cow[i].e==cow[i-1].e&&cow[i].s==cow[i-1].s) num[cow[i].ID] = num[cow[i-1].ID]; else { int t = 0; t = Query(cow[i].s+1); num[cow[i].ID] =t; } Update(cow[i].s+1); } for(int i = 1; i <= N; ++i) { if(i>1) printf(" "); printf("%d",num[i]); } printf("\n"); } return 0; }