火柴排队(c++实现)

本文主要是介绍火柴排队(c++实现)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

---

涵涵有两盒火柴，每盒装有 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);
}

这篇关于火柴排队(c++实现)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---