算法十:最小交换

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

问题描述

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

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

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

输入格式

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

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

输出格式

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

样例输入

  1. 3 (排列长度)
  2. 3 2 1

样例输出

  1. 3

样例解释

你可以:

花 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
using namespace std;

// ================= 代码实现开始 =================
//seq:原序列,为了方便处理,将其设为全局变量
//seqTemp:用以辅助计算的临时数组
//cnt:统计逆序对个数
vector 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 a)
{
seq = a;//复制序列到全局变量
seqTemp.resize(n);//初始化临时数组的长度
cnt = 0;//置零计数量
mergeSort(0, n-1);//进行归并排序
return cnt;//返回答案
}
// ================= 代码实现结束 =================

发表评论

表情:
评论列表 (有 0 条评论,203人围观)

还没有评论,来说两句吧...

相关阅读

    相关 算法交换

    问题描述 给定一个 1 到 n 的排列(即一个序列,其中 \[1,n\] 之间的正整数每个都出现了恰好 1 次)。 你可以花 1 元钱交换两个相邻的数。 现在,你希望把它