树状数组过】"/>
哈理工OJ 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 |
刚看到题目的时候是真的没想到用数据结构相关知识来解，当简单的贪心去考虑的问题。还是太年轻啊~
思路：对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);} }
更多推荐
哈理工OJ 1400 汽车比赛【树状数组过】
发布评论