本文共 1627 字，大约阅读时间需要 5 分钟。

【题目描述】

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

由于位置不同

按位置第一关键字排序后

找速度中的逆序对 即为超车数

因为路是无限长的

存在一组I,J使I位置在J左面 I速度大于J

I就一定会超过J

可以利用归并排序在NlogN时间内求出逆序对

第一次写归并= =

wa了好多次

加入找到t[h1]>t[h2]则需要加上mid-h1+1

因为l-mid已经归并好

t[h1]>t[h2] 则对于h1<=i<=mid  t[i]>t[h2]

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;struct self{int x,y;}s[500033];int cmp(self a1,self a2){return a1.x
       
        >1;    int h1=l,h2=mid+1,i=0;    while(h1<=mid&&h2<=r)    {        if(t[h1]<=t[h2])        {            i++;            temp[i]=t[h1];            h1++;        }        else        {            z=z+(mid-h1+1);            i++;            temp[i]=t[h2];            h2++;        }    }    while(h1<=mid)    {        i++;        temp[i]=t[h1];        h1++;    }    while(h2<=r)    {        i++;        temp[i]=t[h2];        h2++;    }    for(a=l;a<=r;a++)t[a]=temp[a-l+1];}void work(int l,int r){    if(l==r)return;    int mid=(l+r)>>1;    work(l,mid);    work(mid+1,r);    gui(l,r);}    int main(){    freopen("overtaking.in","r",stdin);freopen("overtaking.out","w",stdout);    scanf("%d",&m);    for(a=1;a<=m;a++)scanf("%d%d",&s[a].x,&s[a].y);    sort(s+1,s+m+1,cmp);    for(a=1;a<=m;a++)t[a]=s[a].y;    work(1,m);    cout<
        
         <
        
       
      
     
    
   

转载地址：https://blog.csdn.net/li412302070/article/details/12848875 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！