理工 1400 汽车比赛"/>
哈理工 1400 汽车比赛
汽车比赛 | ||||||
| ||||||
Description | ||||||
XianGe非常喜欢赛车比赛尤其是像达喀尔拉力赛,这种的比赛规模很大,涉及到很多国家的车队的许多车手参赛。XianGe也梦想着自己能举办一个这样大规模的比赛,XianGe幻想着有许多人参赛,那是人山人海啊,不过XianGe只允许最多100000人参加比赛。 这么大规模的比赛应该有技术统计,在XianGe的比赛中所有车辆的起始点可能不同,速度当然也会有差异。XianGe想知道比赛中会出现多少次超车(如果两辆车起点相同速度不同也算发生一次超车)。
| ||||||
Input | ||||||
本题有多组测试数据,第一行一个整数n,代表参赛人数,接下来n行,每行输入两个数据,车辆起始位置X i 和速度 V i(0<Xi,Vi<1000000) | ||||||
Output | ||||||
输出比赛中超车的次数,每组输出占一行 | ||||||
Sample Input | ||||||
2 | ||||||
Sample Output | ||||||
1 | ||||||
Author | ||||||
杨和禹 |
这个是我们理工的题目。树状数组第二次做,独立做出来了 ,不过走了点儿弯路,一开始 是对位置排序 发现这样会导致很复杂,然而 如果直接对速度先排好顺序的话 ,那就会方便好多。注意到如果,位置相同,速度要递增排。
对了
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;const int M=100000+2;
int cnt[M];struct A
{int s,v;
} per[M*10];bool cmp(A a,A b)
{if(a.s==b.s)return a.v<b.v;return a.s>b.s;
}int lowbit(int x)
{return x&(-x);
}
long long sum(int x)
{long long s=0;while(x>0){s+=cnt[x];x-=lowbit(x);}return s;
}void add(int x,int val)
{while(x<=M){cnt[x]+=val;x+=lowbit(x);}
}int main()
{int N;while(cin>>N){int x,y;memset(cnt,0,sizeof(cnt));for(int i=0; i<N; i++){cin>>x>>y;per[i].s=x;per[i].v=y;}sort(per,per+N,cmp);long long result=0;for(int j=0; j<N; j++){add(per[j].v,1);result+=(sum(per[j].v-1));//cout<<"sum="<<sum(per[j].v-1)<<endl<<"result="<<result<<endl;}printf("%lld\n",result);}return 0;
}
/**
4
7 3
2 3
4 6
4 6
*/
更多推荐
哈理工 1400 汽车比赛
发布评论