AcWing 788. 逆序对的数量(Java 版本)
原题链接
简单
作者:
恒心
,
2021-01-20 19:37:53
,
所有人可见
,
阅读 307
import java.io.*;
import java.util.*;
class Main{
public static void main(String[] args) throws Exception{
Scanner sc = new Scanner(System.in);
int N = Integer.parseInt(sc.nextLine());
int[] nums = new int[N];
String[] ss = sc.nextLine().split(" ");
for(int i = 0; i < N; ++i){
nums[i] = Integer.parseInt(ss[i]);
}
System.out.println(mergeSort(nums, 0, nums.length - 1));
}
public static long mergeSort(int[] nums, int start, int end){
if(start >= end) return 0;
int[] temp = new int[end - start + 1];
int k = 0;
int mid = start + (end - start)/2;
int L1 = start;
int L2 = mid + 1;
long res = 0;
res += mergeSort(nums, start, mid) + mergeSort(nums, mid + 1, end);
while(L1 <= mid && L2 <= end){
if(nums[L1] > nums[L2]){
temp[k++] = nums[L2++];
res += (mid - L1) + 1;
}else{
temp[k++] = nums[L1++];
}
}
while(L1 <= mid){
temp[k++] = nums[L1++];
};
while(L2 <= end){
temp[k++] = nums[L2++];
};
for(int i = start, j = 0; i <= end; ++i, ++j){
nums[i] = temp[j];
}
return res;
}
}