AcWing 788. 逆序对的数量
原题链接
简单
作者:
Fu11uck.
,
2024-01-22 20:17:31
,
所有人可见
,
阅读 30
java 代码
import java.util.Scanner;
import java.io.*;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static int[] d=new int[100010];
public static void main(String[] args)throws Exception {
BufferedReader re=new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(re.readLine());
String[] str=re.readLine().split(" ");
for(int i=0;i<n;i++){
d[i]=Integer.parseInt(str[i]);
}
//在此输入您的代码...
// pay(a,0,n-1);//调用由小到大排序方法
System.out.println(pay(0,n-1));
re.close();
// }
}
public static long pay(int l,int r){
if(l>=r)return 0;
int[] temp=new int[r-l+1];
int mid=l+r>>1;
// pay(a,l,mid);//左右递归排序
// pay(a,mid+1,r);
long res=0;
res+=pay(l,mid)+pay(mid+1,r);
int k=0,i=l,j=mid+1;
while(i<=mid&&j<=r){
if(d[i]>d[j]){//取较小者到temp数组
temp[k++]=d[j++];
res+=mid-i+1;
}else{
temp[k++]=d[i++];
}
}
while(i<=mid) temp[k++]=d[i++];
while(j<=r) temp[k++]=d[j++];
for(i=l,j=0;i<=r;i++,j++){//头位置不定在0下标
d[i]=temp[j];
}
return res;
}
}