本文共 3229 字，大约阅读时间需要 10 分钟。
1、
2、题目大意： 有n头牛，每头牛都有一个喜欢的区间[s,e],如果一头牛的区间是[Si,Ei],另一头牛的区间是[Sj,Ej],如果Si<=Sj并且Ei>=Ej,
我们定义为i这头牛比j这头牛更强壮，现在给出这n头牛的各自的区间，求每一头牛比她强壮的个数
3、题目分析
假如说把区间看做是点的坐标，那么这题既可以想成是求每一个点的左上方有多少个点，这跟stars拿到题目就类似了，只不过拿到题目是求左下方的点数，我们将这些点按照y从大到小排序，那么我们只需要看该点的前边有多少个比自己小的点就行了，
这道题目很容易就把样例过了，wrong answer也是特容易的，此题需要注意区间可能有重复的，需要单独考虑，不需要重复计算
4、题目：
| Time Limit: 3000MS | | Memory Limit: 65536K |
| Total Submissions: 11287 | | Accepted: 3719 |
Description
Farmer John's cows have discovered that the clover growing along the ridge of the hill (which we can think of as a one-dimensional number line) in his field is particularly good.
Farmer John has N cows (we number the cows from 1 to N). Each of Farmer John's N cows has a range of clover that she particularly likes (these ranges might overlap). The ranges are defined by a closed interval [S,E].
But some cows are strong and some are weak. Given two cows: cow
i and cow
j, their favourite clover range is [Si, Ei] and [Sj, Ej]. If Si <= Sj and Ej <= Ei and Ei - Si > Ej - Sj, we say that cow
i is stronger than cow
j.
For each cow, how many cows are stronger than her? Farmer John needs your help!
Input
The input contains multiple test cases.
For each test case, the first line is an integer N (1 <= N <= 10
5), which is the number of cows. Then come N lines, the i-th of which contains two integers: S and E(0 <= S < E <= 10
5) specifying the start end location respectively of a range preferred by some cow. Locations are given as distance from the start of the ridge.
The end of the input contains a single 0.
Output
For each test case, output one line containing n space-separated integers, the i-th of which specifying the number of cows that are stronger than cow
i.
Sample Input
31 20 33 40
Sample Output
1 0 0
Hint
Huge input and output,scanf and printf is recommended.
Source
5、AC代码;
#include #include #include using namespace std;#define N 100005int n;int c[N];struct node{ int x; int y; int id;}a[N];int cmp(node a,node b){ if(a.y==b.y) return a.x b.y;}int lowbit(int i){ return i&(-i);}void update(int x,int v){ for(int i=x;i<=N;i+=lowbit(i)) { c[i]+=v; }}int getSum(int x){ int sum=0; for(int i=x;i>0;i-=lowbit(i)) { sum+=c[i]; } return sum;}int main(){ while(scanf("%d",&n)!=EOF) { if(n==0) break; //注意c的初始化问题 memset(c,0,sizeof(c)); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].x,&a[i].y); a[i].x++; a[i].y++; a[i].id=i; } sort(a+1,a+n+1,cmp); int ans[N]; for(int i=1;i<=n;i++) { //先判断是否有重复区间，没有这个if,就wrong answer if(a[i].x==a[i-1].x && a[i].y==a[i-1].y && i>1) { ans[a[i].id]=ans[a[i-1].id]; } else ans[a[i].id]=getSum(a[i].x); update(a[i].x,1); } int flag=0; for(int i=1;i<=n;i++) { if(flag==0) { printf("%d",ans[i]); flag=1; } else printf(" %d",ans[i]); } printf("\n"); } return 0;}/*31 20 33 451 21 32 31 42 431 20 33 4*/
转载地址：http://ewcdi.baihongyu.com/