哈理工OJ 1400 汽车比赛【树状数组过】

时间:2022-09-03 10:32:01
汽车比赛
Time Limit: 1000 MS Memory Limit: 65536 K
Total Submit: 429(116 users) Total Accepted: 165(96 users) Rating: 哈理工OJ 1400 汽车比赛【树状数组过】哈理工OJ 1400 汽车比赛【树状数组过】哈理工OJ 1400 汽车比赛【树状数组过】 Special Judge: No
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

刚看到题目的时候是真的没想到用数据结构相关知识来解,当简单的贪心去考虑的问题。还是太年轻啊~

思路:对n辆车进行排序,按照位子先后顺序,速度从大到小的顺序排序。然后依次update(速度,1)。然后output+=比当前车速度大的车,因为位子是从小到大的,所以之前的车一定是在当前车位子前边(包括当前位子),如果之前的车速度比当前车的速度大,那么就出现了一次超车。

注意数据范围,以及long long

这里直接上代码:

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
struct che
{
int weizi,sudu;
}a[1212122];
int cmp(che a,che b)
{
if(a.weizi==b.weizi)
return a.sudu>b.sudu;
return a.weizi<b.weizi;
}
int c[1000005];
int lowbit(int x)
{
return x&(-x);
}
void add(int u,int v)
{
while(u<=1000005)
{
c[u]+=v;
u+=lowbit(u);
}
}
long long getsum(int u)
{
long long s=0;
while(u>0)
{
s+=c[u];
u-=lowbit(u);
}
return s;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
long long sum=0;
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].weizi,&a[i].sudu);
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
{
add(a[i].sudu,1);
sum+=(i-getsum(a[i].sudu));
// printf("%lld\n",sum);
}
printf("%lld\n",sum);
 }}