【题目描述】 某一时刻，有n辆车在一条很长很长的道路上，它们各自以某种速度匀速前进，如果有两辆车A车和B车，A车在B车的后面，且A车的速度大于B车的速度，那么经过一定的时间后，A车必定会超过B车，这称为一次超车。求超车总数。道路起点的位置为0，没有两辆车的初始位置相同。 【输入格式】 第一行，一个数n，车辆的总数。 第二行~第n+1行，为n辆车的信息，每行有两个正整数x，y。X为起始位置，y为速度。 【输出格式】 超车总数 【样例输入】 2 5 6 2 8 【样例输出】 1 【数据范围】 20%的数据，n<=300 50%的数据，n<=3000 100%的数据，n<=300000 【分析】 不难看出此题就是先按照起始位置排序，再求速度的逆序对。对于50%的数据，可以用双重循环，但是对于所有的数据就要考虑更高效的算法——归并排序。注意最后输出的结果可能很大，所以要使用qword！
var i,n:longint; ans:qword; x,y,b:array[0..300001]of longint; procedure qsort(l,r:longint); var i,j,mid,tmp:longint; begin i:=l;j:=r; mid:=x[(l+r) div 2]; repeat while x[i]<mid do inc(i); while x[j]>mid do dec(j); if i<=j then begin tmp:=x[i];x[i]:=x[j];x[j]:=tmp; tmp:=y[i];y[i]:=y[j];y[j]:=tmp; inc(i);dec(j); end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end; procedure msort(l,r:longint); var i,j,k,mid:longint; begin if l>=r then exit; mid:=(l+r) div 2; msort(l,mid); msort(mid+1,r); i:=l; j:=mid+1; k:=l; while (i<=mid)or(j<=r) do begin if (i<=mid) and ((j>r)or(y[i]<=y[j])) then begin b[k]:=y[i]; inc(i); ans:=ans+j-mid-1; end else begin b[k]:=y[j]; inc(j); end; inc(k); end; for i:=l to r do y[i]:=b[i]; end; begin readln(n); for i:=1 to n do readln(x[i],y[i]); qsort(1,n); ans:=0; msort(1,n); write(ans); end.转载于:https://www.cnblogs.com/JRX2015U43/p/6533530.html
相关资源：“换道超车”:新时代经济高质量发展路径创新