题目
涵涵有两盒火柴,每盒装有 n 根火柴,每根火柴都有一个高度。
现在将每盒中的火柴各自排成一列,同一列火柴的高度互不相同,两列火柴之间的距离定义为:
其中 ai 表示第一列火柴中第 i 个火柴的高度,bi 表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。
请问得到这个最小的距离,最少需要交换多少次?
如果这个数字太大,请输出这个最小交换次数对 99,999,997 取模的结果。
输入
共三行,第一行包含一个整数 n,表示每盒中火柴的数目。
第二行有 n 个整数,每两个整数之间用一个空格隔开,表示第一列火柴的高度。
第三行有 n 个整数,每两个整数之间用一个空格隔开,表示第二列火柴的高度。
输出
输出共一行,包含一个整数,表示最少交换次数对 99,999,997
取模的结果。
样例
输入样例:
4
2 3 1 4
3 2 1 4
输出样例:
1
思路
首先我们可以假定a已经是升序排列的数组,然后如果我们想要让结果最小的话,b一定也要是升序的,所以我们可以转化为求逆序对的数量,首先我们定义几个数组,a,b不用解释了,然后第一步,我们把a数组中的每个元素,存在p中,p中存的是a中每个元素第几小,然后在把结果赋给a,b也是一样。为什么要这样,这样可以缩小a的范围,这样缩小并不对结果产生什么影响,因为结果主要考虑相对大小。总的来说,第一步就是缩小范围。
然后第二步
第二步首先在数组c中存放a[i],也就是说 a[i] 就是 c的下标。
c[a[i]] = i;
然后第三步
第三步就是 b 中存放 b[i] 在 c的位置 ,为什么要这么做,是因为,这么做就知道 b 和 a的相对位置了。为什么这么做b[i]一定有对应的a[i]?是因为 我们第一步就做了工作,此时a b 中存放的都是 相对位置,也就是第几小;
最后一步
就直接求b中逆序对的数量 就出来了
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, MOD = 99999997;
int n;
int a[N], b[N], c[N], p[N];
void work(int a[]){
for(int i=0;i<n;i++) p[i] = i;
sort(p,p+n,[&](int x,int y){
return a[x]<a[y];
});
for(int i=0;i<n;i++) a[p[i]] = i;
}
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;
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
for(int i=0;i<n;i++) scanf("%d",&b[i]);
work(a),work(b);
for(int i=0;i<n;i++) c[a[i]] = i;
for(int i=0;i<n;i++) b[i] = c[b[i]];
int res = merge_sort(0,n-1);
printf("%d",res);
}