【题目来源】https://www.luogu.com.cn/problem/P1966【题目描述】涵涵有两盒火柴每盒装有 n 根火柴每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列 同一列火柴的高度互不相同 两列火柴之间的距离定义为∑(aᵢ−bᵢ)²。其中 aᵢ 表示第一列火柴中第 i 个火柴的高度bᵢ 表示第二列火柴中第 i 个火柴的高度。每列火柴中相邻两根火柴的位置都可以交换请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离最少需要交换多少次如果这个数字太大请输出这个最小交换次数对 10⁸−3 取模的结果。【输入格式】共三行第一行包含一个整数 n表示每盒中火柴的数目。第二行有 n 个整数每两个整数之间用一个空格隔开表示第一列火柴的高度。第三行有 n 个整数每两个整数之间用一个空格隔开表示第二列火柴的高度。【输出格式】一个整数表示最少交换次数对 10⁸−3 取模的结果。【输入样例】41 3 4 21 7 2 4【输出样例】2【数据范围】对于10%的数据1≤n≤10对于30%的数据1≤n≤100对于60%的数据1≤n≤10^3对于100%的数据1≤n≤10^50≤ai,bi2^31且对于任意1≤ij≤nai≠ajbi≠bj。【算法分析】● 离散化‌是一种将一组不连续、无规律或取值范围很大的数据转换成一个从小到大的整数序列的方法使得我们可以使用数组下标来处理原本无法直接处理的值。通过离散化可以将无限空间中的有限个体映射到有限的空间中去从而提高算法的时空效率‌。● 将稀疏分布的大范围数据压缩映射到紧凑连续空间是离散化的典型操作。例如将数值差距大的非连续点如 1, 999, 100000映射为连续的数组下标如 1, 2, 3同时保持数据相对大小关系不变。● 离散化是一种数据处理的技巧。可以进行离散化的数据有大整数、浮点数、字符串等。● 简单而言常用的离散化算法步骤为“排序、去重、映射”。在 C 中离散化常用lower_bound()或STL map实现。【算法代码一lower_bound离散化】lower_bound(t1, tn1, a[i]) 的作用是在有序数组​ t 中找到第一个 ≥ a[i] 的元素的地址。原因在于 a[i]一定在 t 中且 t 是已排序的所以通过命令a[i]lower_bound(t1,tn1,a[i])-t;得到的就是 a[i] 在 t 中的位置。#include bits/stdc.h using namespace std; const int MOD1e8-3; const int N1e55; int a[N],b[N]; int t[N]; //临时数组 int c[N]; //逆序对数组 long long ans; void discretize(int a[],int n) { for(int i1; in; i) t[i]a[i]; sort(t1,tn1); for(int i1; in; i) { a[i]lower_bound(t1,tn1,a[i])-t; } } void merge_sort(int le,int ri) { if(leri) return; int mid(leri)1; merge_sort(le,mid); merge_sort(mid1,ri); int ple; int ile,jmid1; while(imid jri) { if(c[i]c[j]) t[p]c[i]; else { t[p]c[j]; ansmid-i1; } } while(imid) t[p]c[i]; while(jri) t[p]c[j]; for(int kle; kri; k) c[k]t[k]; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cinn; for(int i1; in; i) cina[i]; for(int i1; in; i) cinb[i]; discretize(a,n); discretize(b,n); for(int i1; in; i) t[b[i]]i; for(int i1; in; i) c[i]t[a[i]]; merge_sort(1,n); coutans%MODendl; return 0; } /* in: 4 1 3 4 2 1 7 2 4 out: 2 */【算法代码二STL map离散化】#include bits/stdc.h using namespace std; const int MOD1e8-3; const int N1e55; int a[N],b[N]; int t[N]; //临时数组 int c[N]; //逆序对数组 long long ans; void discretize(int a[], int n) { mapint,int mp; for(int i1; in; i) mp[a[i]]0; int rk0; for(auto x:mp) x.secondrk; for(int i1; in; i) a[i]mp[a[i]]; } void merge_sort(int le,int ri) { if(leri) return; int mid(leri)1; merge_sort(le,mid); merge_sort(mid1,ri); int ple; int ile,jmid1; while(imid jri) { if(c[i]c[j]) t[p]c[i]; else { t[p]c[j]; ansmid-i1; //统计逆序对 } } while(imid) t[p]c[i]; while(jri) t[p]c[j]; for(int kle; kri; k) c[k]t[k]; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cinn; for(int i1; in; i) cina[i]; for(int i1; in; i) cinb[i]; discretize(a,n); discretize(b,n); //构造c[]数组a[]的排名 -- b[]的位置 for(int i1; in; i) t[b[i]]i; for(int i1; in; i) c[i]t[a[i]];; merge_sort(1,n); coutans%MODendl; return 0; } /* in: 4 1 3 4 2 1 7 2 4 out: 2 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/145679752https://blog.csdn.net/hnjzsyjyj/article/details/143275575https://www.luogu.com.cn/problem/solution/P1966