题意:FJ有n头牛(编号为1~n),每一头牛都有一个测验值[S, E],如果对于牛i和牛j来说,它们的测验值满足下面的条件则证明牛i比牛j强壮:Si <= Sj and Ej <= Ei and Ei - Si > Ej - Sj。现在已知每一头牛的测验值,要求输出每头牛有几头牛比其强壮。
思路:树状数组。需要对牛i比牛j强壮的条件进行理解。把牛群按照测验值E的降序排序,(E相等按S的升序),那么接着就只需考虑S值,如果当前牛的测验值为[s, e],那么比它强壮的牛的个数,就等于排序在它前面的,S值在[0,s]区间的牛数量(E相等的话为[0,s-1])。下面的就是树状数组部分了。此外还要考虑,如果存在两头牛区间一致的情况,只需要在求和的基础上减去就行了。总体而言这道题目和star的那个题目完全类型一致。
#include <iostream> #include <algorithm> using namespace std; const int Max=100005; struct data { int id,s,e; }pre,cow[Max]; int n,ar[Max],maxval; int lowbit(int i) { return i&(-i); } int max(int a,int b) { return a>b?a:b; } bool cmp(data a,data b) { if(a.e==b.e) return a.s<b.s; else return a.e>b.e; } void add(int i) { while (i<=maxval) { ar[i]+=1; i+=lowbit(i); } } int sum(int i) { int ans=0; while (i>0) { ans+=ar[i]; i-=lowbit(i); } return ans; } int main() { int i,s,e,ans[Max]; while (scanf("%d",&n)&&n) { memset(ar,0,sizeof(ar)); maxval=0; for (i=0;i<n;i++) { scanf("%d%d",&s,&e); s++,e++;//加一的目的是为了避免0的出现 cow[i].s=s; cow[i].e=e; cow[i].id=i; maxval=max(maxval,cow[i].s); } sort(cow,cow+n,cmp); int cnt=0; pre.s=pre.e=-1; for (i=0;i<n;i++) { if (cow[i].s==pre.s&&cow[i].e==pre.e)//如果两个牛的区间相同的处理 cnt++; else { cnt=0; pre.s=cow[i].s; pre.e=cow[i].e; } ans[cow[i].id]=sum(cow[i].s)-cnt; add(cow[i].s); } for (i=0;i<n;i++) printf("%d ",ans[i]); printf("\n"); } return 0; }