万能小偷程序做网站,保山网站建设报价,微信商城怎么找,搭建网页游戏题目
题意:
有一群牛#xff0c;每个牛有两个属性值[S,E]#xff0c;如果牛i和牛j属性值满足Si Sj 且 Ej Ei 且 Ei - Si Ej - Sj#xff0c;牛i比牛j强壮#xff0c;输出每个牛比自己强壮的牛的数量。
题解#xff1a;
我们可以把[S,E]看作坐标#x…题目
题意:
有一群牛每个牛有两个属性值[S,E]如果牛i和牛j属性值满足Si Sj 且 Ej Ei 且 Ei - Si Ej - Sj牛i比牛j强壮输出每个牛比自己强壮的牛的数量。
题解
我们可以把[S,E]看作坐标条件Si Sj 且 Ej Ei 且 Ei - Si Ej - Sj其实就是求每个点左上角有多少点 我们先将e按照降序然后s按照升序 这样的话越往前的牛越弱 我们可以用树状数组来求和计算
代码
#include iostream
using namespace std;
#include stdio.h
#include memory.h
#include algorithm
struct COW{int start;int end;int index;
};
#define maxn 100010
COW cow[maxn];
bool cmp(const struct COW x, const struct COW y) {if (x.endy.end)return x.start y.start;return x.end y.end;
}
int n,c[maxn],ans[maxn];
int lowbit(int x) {return x(-x);
}void add(int i, int val) {while (in) {c[i]val;ilowbit(i);}
}
//求前i项元素的和
int get_sum(int i) {int sum0;while (i0) {sumc[i];i-lowbit(i);}return sum;
}
int main()
{int i,j,k;scanf(%d,n);while (n!0) {for (i0;in;i) {scanf(%d%d,cow[i].start,cow[i].end);cow[i].start;cow[i].end;cow[i].indexi;}memset(c,0,sizeof(c));sort(cow,cown,cmp);for (i0;in;i) {if (i0cow[i].startcow[i-1].startcow[i].endcow[i-1].end)ans[cow[i].index]ans[cow[i-1].index];else ans[cow[i].index]get_sum(cow[i].start);add(cow[i].start,1);}for (i0;in;i)printf(%d%c,ans[i],i(n-1)?\n: );scanf(%d,n);}return 0;
}
