树状数组)"/>
[ACM] hrbustoj 1400 汽车比赛 (树状数组)
汽车比赛 | ||||||
| ||||||
Description | ||||||
XianGe非常喜欢赛车比赛尤其是像达喀尔拉力赛,这种的比赛规模很大,涉及到很多国家的车队的许多车手参赛。XianGe也梦想着自己能举办一个这样大规模的比赛,XianGe幻想着有许多人参赛,那是人山人海啊,不过XianGe只允许最多100000人参加比赛。 这么大规模的比赛应该有技术统计,在XianGe的比赛中所有车辆的起始点可能不同,速度当然也会有差异。XianGe想知道比赛中会出现多少次超车(如果两辆车起点相同速度不同也算发生一次超车)。 | ||||||
Input | ||||||
本题有多组测试数据,第一行一个整数n,代表参赛人数,接下来n行,每行输入两个数据,车辆起始位置X i 和速度 V i(0<Xi,Vi<1000000) | ||||||
Output | ||||||
输出比赛中超车的次数,每组输出占一行 | ||||||
Sample Input | ||||||
2 2 1 2 2 5 2 6 9 4 3 1 4 9 9 1 7 5 5 6 10 5 6 3 10 9 10 9 5 2 2 | ||||||
Sample Output | ||||||
1 6 7 | ||||||
Author | ||||||
杨和禹 |
给出n个汽车的起始位置和速度,问总共可以发生多少次超车,位置相同,速度不一样也算一次超车。
位置小速度大的车肯定能超过位置大速度小的车。把n个车按起始位置从小到大,如果相等按速度从大到小进行排序。用树状数组进行统计,区间为速度大小,对第j辆车来说,假设他的速度为v,则首先更新vn[v] ++,并利用lowbit向上更新,因为这是第j辆车,统计区间【1,v】的速度有多少辆车(包括自己),这些车是不可能超过它的,那么j- sum(v)则是前j辆车有多少辆可以超过当前的车,也就是超车的次数。
拿第二组测试数据为例:
5
2 6
9 4
3 1
4 9
9 1
排序后
2 6
3 1
4 9
9 4
9 1
速度 1 2 3 4 5 6 7 8 9
多少辆 2 0 0 1 0 1 0 0 1
拿最后一个数据具体说明 9 1 ,这是第5辆车,他的速度为v,在他之前速度小于等于它的有两辆(包括自身),那么前面能够超过它的车有 5-2=3辆 ,对于每辆车都统计出前面能够超过它的车有多少辆,加起来就是所求的超车次数了。
代码:
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn=100002;
const int maxv=1000002;
int vn[maxv];struct Car
{int x;int v;
}car[maxn];bool cmp(Car a,Car b)//先按位置从小到大进行排序,如果位置相等,按速度从大到小进行
{if(a.x<b.x)return true;else if(a.x==b.x){if(a.v>=b.v)return true;return false;}return false;
}int lowbit(int x)
{return x&(-x);
}void update(int p,int max)
{while(p<=max){vn[p]++;p+=lowbit(p);}
}int sum(int p)//这题这里的意思是前p辆车中比当前车速度小或相等的车有几辆(包括它自己)
{int s=0;while(p>0){s+=vn[p];p-=lowbit(p);}return s;
}int main()
{int n;while(cin>>n){memset(vn,0,sizeof(vn));int max=0;for(int i=1;i<=n;i++){cin>>car[i].x>>car[i].v;if(max<car[i].v)max=car[i].v;}sort(car+1,car+1+n,cmp);long long ans=0;for(int i=1;i<=n;i++){update(car[i].v,max);ans=ans+(i-sum(car[i].v));//i-sum(car[i].v)的意思是前i辆车里面有几辆能够超过它}cout<<ans<<endl;}return 0;
}
更多推荐
[ACM] hrbustoj 1400 汽车比赛 (树状数组)
发布评论