问题 B: 超车
时间限制: 1 Sec 内存限制: 128 MB
提交: 26 解决: 4
[提交][状态]
题目描述
Jzabc对赛车也很感兴趣，在参观车展是，想到这样一个问题，在某时刻，他看到n辆车（总是匀速行驶）在同一直线上，且处于一个无限长的直道上，而且n辆车有严格的先后之分，。他通过特殊的器材测出了每辆车的速度，那么问题出现了，如果有车A和车B，A在B的后面，且A的速度快于B的，那么经过一段时间后，A一定会超过B，我们称之为一次超车。那么他想请你帮忙计算超车总数。我们记车道起点的坐标为0 ，没有两辆车的坐标相同。

输入
第一行，一个数N，表示车辆总数。以下n行为N辆车的信息； 第二行至第N+1行，每行有两个正整数X、Y，X和Y之间有一个空格，其中X为车的坐标，Y为车的速度。 0<=X,Y<=1000000000

输出
一行，超车总数

样例输入
2
5 6
2 8
样例输出
1
提示

对于20%的数据，满足N<=300

对于50%的数据，满足N<=3000

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

#include<cstdio> 
#include<algorithm> 
#include<cstring> 
#include <iostream> 
#define mo 100000000 
#define int long long 
using namespace std;   
int n; 
struct NODE{ 
    int x,v; 
}dmf[300005]; 
int t[300005]; 
int tem[300005]; 
inline bool cmp(NODE a,NODE b){ 
    return a.x<b.x; 
} 
int ans=0; 
void gui(int l,int r){ 
    int i=l; 
    int mid=l+r>>1; 
    int j=mid+1; 
    int k=l; 
    while(i<=mid&&j<=r){ 
        if(t[i]>t[j]){ 
            tem[k++]=t[j++]; 
            ans+=mid-i+1; 
        } 
        else{ 
            tem[k++]=t[i++]; 
        } 
    } 
    while(i<=mid) tem[k++]=t[i++]; 
    while(j<=r) tem[k++]=t[j++]; 
    for(int i=l;i<=r;i++) 
     t[i]=tem[i]; 
} 
void work(int l,int r){ 
    if(l<r) 
    { 
        int mid=l+r>>1; 
        work(l,mid); 
        work(mid+1,r); 
        gui(l,r);        
    } 

} 
main(){ 
    scanf("%lld",&n); 
    for(int i=1;i<=n;i++){ 
        scanf("%lld%lld",&dmf[i].x,&dmf[i].v); 
    } 
    sort(dmf+1,dmf+n+1,cmp); 
    for(int i=1;i<=n;i++) t[i]=dmf[i].v; 
    work(1,n); 
    cout<<ans; 
    return 0; 
}

这题没啥用，就是复习下逆序对hiahiahia