算法十：最小交换

桃扇骨 2022-05-24 11:12 174阅读 0赞

**问题描述**

给定一个 1 到 n 的排列（即一个序列，其中 \[1,n\] 之间的正整数每个都出现了恰好 1 次）。

你可以花 1 元钱交换两个相邻的数。

现在，你希望把它们**升序排序**。求你完成这个目标最少需要花费多少元钱。

### 输入格式 ###

第一行一个整数 n，表示排列长度。

接下来一行 n 个用空格隔开的正整数，描述这个排列。

### 输出格式 ###

输出一行一个非负整数，表示完成目标最少需要花多少元钱。

### 样例输入 ###

3 （排列长度）
    3 2 1

### 样例输出 ###

### 样例解释 ###

你可以：

花 1 元交换 1,2，序列变成 3 1 2。

花 1 元交换 1,3，序列变成 1 3 2。

花 1 元交换 2,3，序列变成 1 2 3。

总共需要花 3 元。

可以证明不存在更优的解。

### 提示 ###

\[每次交换相邻的两个数都会使逆序对 +1 或 -1。\]

\[逆序对数目不为零时，一定存在相邻的逆序对。\]

\[因此最优策略显然是每次都让逆序对数目 -1。\]

\[所以答案即为逆序对数目。\]

\[朴素的算法时间复杂度是 O(n^2) 的。\]

\[用归并排序求逆序对数可以通过本题。需要提醒的是，答案可能超过 32 位整数的范围哦。\]

\[逆序对数目同样可以用树状数组优化朴素的 O(n^2) 算法，并获得和归并排序相同的时间复杂度。\]

### 一. 伪代码 ###

![70][]

### 二. 具体实现（C++） ###

\#include <bits/stdc++.h>  
using namespace std;  
  
// ================= 代码实现开始 =================  
//seq:原序列，为了方便处理，将其设为全局变量  
//seqTemp：用以辅助计算的临时数组  
//cnt：统计逆序对个数  
vector<int> seq,seqTemp;  
long long cnt;  
//归并排序  
//l，r分别为归并排序排序区间的左右端点  
void mergeSort(int l,int r)\{  
if(l==r)  
return;  
int mid = (l + r)>>1;  
mergeSort(l, mid);//递归，排序mid以左的部分  
mergeSort(mid + 1, r);//递归，排序mid以右的部分  
int p = l,q = mid + 1;//用两个指针来指向归并时需要比较的两个元素  
for(int i = l; i <= r; ++i)\{  
if(q>r || p <= mid && seq\[p\] <= seq\[q\])//判断哪个元素更小  
seqTemp\[i\] = seq\[p++\];//如果左边的元素更小，则将右边的元素插入末尾  
else\{  
seqTemp\[i\] = seq\[q++\];//如果右边的元素更小，则将左边的元素插入末尾  
cnt += mid - p + 1;//并统计产生的逆序对数目  
\}  
\}  
for(int i = l; i <= r; ++i)  
seq\[i\] = seqTemp\[i\];//将排序后的序列复制回原序列的对应位置  
\}  
  
// 这个函数的功能是计算答案（即最少花费的金钱）  
// n：表示序列长度  
// a：存储整个序列 a  
// 返回值：最少花费的金钱（需要注意，返回值的类型为 64 位有符号整数）  
long long getAnswer(int n, vector<int> a)  
\{  
seq = a;//复制序列到全局变量  
seqTemp.resize(n);//初始化临时数组的长度  
cnt = 0;//置零计数量  
mergeSort(0, n-1);//进行归并排序  
return cnt;//返回答案  
\}  
// ================= 代码实现结束 =================

[70]: /images/20220524/76e0273c4f574e719c7c0dc50d837b21.png