还是树状数组的说~\(≧▽≦)/~
题意:给了n头牛,分别给出s和e的值,如果对于牛i和牛j来说,它们的测验值满足下面的条件则证明牛i比牛j强壮:Si <= Sj and Ej <= Ei and Ei - Si > Ej - Sj。现在已知每一头牛的测验值,要求输出每头牛有几头牛比其强壮。
这个要排序的说~,为了保证前面的牛都一定不比后面的牛弱,就要按照e值的降序排列,e值相等时按照s值的升序排列,然后就是求出比当前的牛弱小的牛的个数输出就可以啦。
要注意的地方还是不少的,比如牛的顺序,所以node 中包含了一个int值id,用来记录这个牛的序号,包括存储个数的数组也是按照id的顺序来存储的。为了防止输入值有0的情况产生求和数组下标要从1开始。【话说这个题真的感觉好麻烦的说。。。::>_<::】
#include <iostream> #include <cstdio> #include <string.h> #include <algorithm> using namespace std; const int maxn=100010; int c[maxn],ans[maxn],n,m; struct node { int id,s,e; }cow[100010]; bool cmp(node a,node b) { if(a.e==b.e) return a.s<b.s; return a.e>b.e; } int lowbit(int i) { return i&(-i); } int sum(int x) { int ans=0; while(x>0) { ans+=c[x]; x-=lowbit(x); } return ans; } void update(int x,int val) { while(x<=m) { c[x]+=val; x+=lowbit(x); } } int main() { int i,j,k; while(scanf("%d",&n),n) { m=0; memset(c,0,sizeof(c)); for(i=1;i<=n;i++) { scanf("%d%d",&cow[i].s,&cow[i].e); cow[i].id=i; ++cow[i].s;++cow[i].e; if(cow[i].s>m) m=cow[i].s; } sort(cow+1,cow+n+1,cmp); for(i=1;i<=n;i++) { if(i==1) { ans[cow[i].id]=sum(cow[i].s); update(cow[i].s,1); } else { if(cow[i].s==cow[i-1].s&&cow[i].e==cow[i-1].e) ans[cow[i].id]=ans[cow[i-1].id]; else ans[cow[i].id]=sum(cow[i].s); update(cow[i].s,1); } } for(i=1;i<n;i++) printf("%d ",ans[i]); printf("%d\n",ans[i]); } }
ps:半夜做题的时候脑子不是很清晰的说。。又犯了低级错误。。卡了好久的哇。。。。。