漂移

题目描述

假设赛道是一条无限长的直线，每辆车都以某种速度匀速前行。如果A车一开始在B车后面，且A车的速度大于B车，那么一段时间后，A车必定会超过B车，这种情况称之为一次超车。请你计算一共会发生多少次超车。

输入

第一行输入一个正整数N，表示赛车的数量。 接下来N行，每行两个正整数，分别表示第i辆车的起始位置和速度，数据保证所有车的初始位置不同。

输出

一行，输出超车次数。

数据范围

对于30%的数据，N<=300

对于60%的数据，N<=3000

对于100%的数据，N<=300000

汽车位置和速度 <= $10^6$

样例

输入：

2
5 6
2 8

输出：

1

思路：

求速度的逆序对数量（下标：起始位置）

代码(65pts):

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int st,v;
	friend bool operator < (node x,node y)
	{
		return x.st<y.st;
	}
}x[300005];
int n,cnt;
int a[1000005];
int b[1000005];
void merge(int l,int r)
{
	int mid=(l+r)/2;
	int i=l,j=mid+1,tot=0;
	while(i<=mid&&j<=r)
	{
		if(a[i]<=a[j])
		{
			b[++tot]=a[i];
			++i;
		}
		else
		{ 
			b[++tot]=a[j];
			++j;
			cnt+=(mid-i+1);
		}
	} 
	while(i<=mid) b[++tot]=a[i],++i;
	while(j<=r) b[++tot]=a[j],++j;
	for(int i=1;i<=tot;i++) a[l+i-1]=b[i];
}
void merge_sort(int l,int r)
{
	if(l>=r) return;
	int mid=(l+r)/2;
	merge_sort(l,mid);
	merge_sort(mid+1,r);
	merge(l,r);
}
int main()
{
	cin >> n;
	for(int i=1;i<=n;i++)
		cin >> x[i].st >> x[i].v;
	sort(x+1,x+n+1);
	for(int i=1;i<=n;i++)
		a[i]=x[i].v; 
	merge_sort(1,n);
	cout << cnt;
    return 0;
}