逆序数)"/>
HLG 1400 汽车比赛 (11年黑龙江省赛)树状数组(逆序数)
链接:.php?m=ProblemSet&a=showProblem&problem_id=1400
Description:
XianGe非常喜欢赛车比赛尤其是像达喀尔拉力赛,这种的比赛规模很大,涉及到很多国家的车队的许多车手参赛。XianGe也梦想着自己能举办一个这样大规模的比赛,XianGe幻想着有许多人参赛,那是人山人海啊,不过XianGe只允许最多100000人参加比赛。 这么大规模的比赛应该有技术统计,在XianGe的比赛中所有车辆的起始点可能不同,速度当然也会有差异。XianGe想知道比赛中会出现多少次超车(如果两辆车起点相同速度不同也算发生一次超车)。Input: 本题有多组测试数据,第一行一个整数n,代表参赛人数,接下来n行,每行输入两个数据,车辆起始位置X i 和速度 V i(0<Xi,Vi<1000000)
Output: 输出比赛中超车的次数,每组输出占一行
思路:这道题跟POJ 3067 Japan很像,基本上是一样的思路和方法,详细请看我博客上一贴;
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN 1000000
using namespace std;int c[MAXN], MAXV;struct point
{int x, v;
};
point car[MAXN];int lowbit(int x){ return x & (-x); }void add(int x,int val)
{int i = x;while(i <= MAXV) {c[i] += val;i += lowbit(i);}
}int get_sum(int x)
{int s = 0;while(x > 0) {s += c[x];x -= lowbit(x);}return s;
}int cmp(point Y1, point Y2)
{if(Y1.x != Y2.x) return Y1.x < Y2.x;else return Y1.v > Y2.v;
}int main()
{int n;long long sum;while(scanf("%d", &n)!=EOF) {MAXV = 0;memset(c, 0, sizeof(c));for(int i=1; i<=n; i++) {scanf("%d%d", &car[i].x, &car[i].v);if(MAXV < car[i].v)MAXV = car[i].v;}sort(car, car+n+1, cmp);sum = 0;for(int i=1; i<=n; i++) {//cout<<car[i].x<<" "<<car[i].v<<endl;add(car[i].v, 1);sum += i-get_sum(car[i].v);}printf("%lld\n", sum);}return 0;
}
更多推荐
HLG 1400 汽车比赛 (11年黑龙江省赛)树状数组(逆序数)
发布评论