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

本文主要是介绍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

输出样例：

题解

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;}}

思路

——这道题具有一定的难度，首先我们要了解一件事，假如有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（逆序对）