五 505. 火柴排队 (归并排序|离散化)

五 505. 火柴排队 (归并排序|离散化)

思路：先将两组数组按(2 3 1 4 -> 2 0 1 3; 3 2 1 4 -> 2 1 0 3)规则排序，然后使用c数组建立双方的映射，从c[ai[i]]=bi[i]，接着就是使用归并排序求c数组的逆序对即交换次数。

import java.util.*;

public class Main {
    private static int res;
    private static int mod = (int) (1e8 - 3);
    
    private static void merge_sort(int l, int r, Integer[] a) {
        if(l == r) return;
        int mid = l + ((r - l) >> 1);
        merge_sort(l, mid, a);
        merge_sort(mid + 1, r, a);
        int i = l, j = mid + 1, k = 0;
        int[] temp = new int[r - l + 1];
        while (i <= mid && j <= r) {
            if(a[i] > a[j]) {
                res = (res + mid - i + 1) % mod;
                temp[k++] = a[j++]; 
            }
            else {
                temp[k++] = a[i++];
            }
        }
        while(i <= mid) {
            temp[k++] = a[i++];
        }
        while(j <= r) {
            temp[k++] = a[j++];
        }
        for(int m = l, n = 0; l <= r && n < temp.length; m++, n++) {
            a[m] = temp[n];
        }
    }
    
    private static void work(Integer[] ai, int[] a, int n) {
        for (int i = 0; i < n; i++) {
            ai[i] = i;
        }
        Arrays.sort(ai, (o1, o2) -> Integer.compare(a[o1], a[o2]));
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            b[i] = sc.nextInt();
        }
        Integer[] ai = new Integer[n], bi = new Integer[n];
        work(ai, a, n);
        work(bi, b, n);
        Integer[] c = new Integer[n];
        for (int i = 0; i < n; i++) {
            c[ai[i]] = bi[i];
        }
        merge_sort(0, n-1, c);
        System.out.println(res);
    }
}