AcWing 788. 逆序对的数量Java
原题链接
简单
作者:
长街听风
,
2021-01-24 21:25:14
,
所有人可见
,
阅读 300
Java 代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] arr = new int[n];
int[] temp = new int[n];
for(int i = 0;i < n;i++){
arr[i] = scanner.nextInt();
}
long res = mergeSort(arr,0,n-1,temp);
System.out.println(res);
}
private static long mergeSort(int[] arr, int l, int r,int[] temp) {
if(l >= r) return 0;//实际结束时,一定时l==r,即只有一个数了
int mid = l + r >> 1;
//左右两边的逆序对数量
long res = mergeSort(arr,l,mid,temp) + mergeSort(arr,mid+1,r,temp);
//合并
int i = l,j = mid + 1,k = 0;
while(i <= mid && j <= r){
if(arr[i] <= arr[j]){
temp[k++] = arr[i++];
}else{
temp[k++] = arr[j++];
res += mid - i + 1;//arr[i]~arr[mid]均与arr[j]构成了逆序对,共mid-i+1对
}
}
//扫尾,下面两个while循环同一轮只会执行其中一个,即其中一边还没有遍历结束的会执行扫尾
while(i <= mid) temp[k++] = arr[i++];
while(j <= r) temp[k++] = arr[j++];
//将本次合并排序后的数放回原数组[l,r]的位置去
for(i = l,k = 0;i <= r;i++,k++){
arr[i] = temp[k];
}
return res;
}
}