AcWing.505 火柴排队(离散化&逆序对)

题目

涵涵有两盒火柴，每盒装有 n
 根火柴，每根火柴都有一个高度。

现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：

∑i=1n(ai−bi)2
其中 ai表示第一列火柴中第 i个火柴的高度，bi表示第二列火柴中第 i个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。

请问得到这个最小的距离，最少需要交换多少次？

如果这个数字太大，请输出这个最小交换次数对 99999997取模的结果。

输入格式

共三行，第一行包含一个整数 n，表示每盒中火柴的数目。

第二行有 n个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。

第三行有 n个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

输出格式

输出共一行，包含一个整数，表示最少交换次数对 99,999,997取模的结果。

数据范围

1≤n≤10⁵
0≤火柴高度≤231−1

• 输入样例：

4
2 3 1 4
3 2 1 4
1
2
3

• 输出样例：

1
1

题解

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author akuya
 * @create 2024-03-14-19:38
 */
public class Main {
    static int N=100010,MOD=99999997;
    static int n;
    static int a[]=new int[N];
    static int b[]=new int[N];
    static int c[]=new int[N];
    static int p[]=new int[N];

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        for(int i=1;i<=n;i++){
            a[i]=scanner.nextInt();
        }
        for(int i=1;i<=n;i++){
            b[i]=scanner.nextInt();
        }

        work(a);
        work(b);

        for(int i=1;i<=n;i++) c[a[i]]=i;
        for(int i=1;i<=n;i++) b[i]=c[b[i]];
        System.out.println(merge_sort(1,n));

    }

    public static int find(int x){
        int l=1,r=n;
        while(l<r){
            int mid=l+r>>1;
            if(p[mid]>=x)r=mid;
            else l=mid +1;
        }
        return r;
    }

    public static void work(int a[]){
        for(int i=1;i<=n;i++)p[i]=a[i];
        Arrays.sort(p,1,n+1);
        for(int i=1;i<=n;i++)a[i]=find(a[i]);
    }

    public static int merge_sort(int l,int r){
        if(l>=r) return 0;

        int mid=l+r>>1;
        int res=merge_sort(l,mid)+merge_sort(mid+1,r)%MOD;

        int i=l,j=mid+1,k=0;
        while(i<=mid&&j<=r){
            if(b[i]<=b[j]) p[k++]=b[i++];
            else{
                p[k++]=b[j++];
                res=(res+mid-i+1)%MOD;
            }
        }

        while(i<=mid) p[k++]=b[i++];
        while(j<=r) p[k++]=b[j++];
        for(i=l,j=0;i<=r;i++,j++) b[i]=p[j];
        return res;

    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

思路

——这道题具有一定的难度，首先我们要了解一件事，假如有a和b两个数列，连个数列有序，那么对应编号的ai与bi的差的绝对值之和最小，这个有严格的数学证明，这里就不证明了，博主是参考正方形思想，相同周长正方形周长最小的思想来类比得到这个结论，没有具体证明。
——当然数组不一定需要有序，两个无序数组只要让其达到对应数字在相同位置就行，这样就需要交换位置。如果考虑a数组有序，那么b数组只需要移动逆序对数的次数，但题目中ab数组都无序，那么，就首先使用两次离散化，使a数组依次离散为1,2，3…类似的有序数组，再将b数组根据a数组的离散下标进行对应的离散。这时，只需要求b数组的逆序对，就为最少交换次数了。
对应下图

逆序对的求取使用归并排序，离散化使用二分法，大家可以去看博主的其他博客了解，这里放下链接。
https://blog.csdn.net/qq_62235017/article/details/131343435（离散化）
https://blog.csdn.net/qq_62235017/article/details/132129447（逆序对）