最小交换发表时间：2022-10-27 20:22 最小交换
时间限制：4 sec 空间限制：256 MB 问题描述 给定一个 1 到 n 的排列（即一个序列，其中 [1,n] 之间的正整数每个都出现了恰好 1 次）。 你可以花 1 元钱交换两个相邻的数。 现在，你希望把它们升序排序。求你完成这个目标最少需要花费多少元钱。 输入格式 第一行一个整数 n，表示排列长度。 接下来一行 n 个用空格隔开的正整数，描述这个排列。 输格式 输出一行一个非负整数，表示完成目标最少需要花多少元钱。 样例输入 样例输 样例解释 你可以： 花 1 元交换 1,2，序列变成 3 1 2。 花 1 元交换 1,3，序列变成 1 3 2。 花 1 元交换 2,3，序列变成 1 2 3。 总共需要花 3 元。 可以证明不存在更优的解。 数据范围 对于 20% 的数据，保证 n<=7。 对于 60% 的数据，保证 n<=1,000。 对于 100% 的数据，保证 n<=200,000。 提示 [每次交换相邻的两个数都会使逆序对 +1 或 -1。] [逆序对数目不为零时，一定存在相邻的逆序对。] [因此最优策略显然是每次都让逆序对数目 -1。] [所以答案即为逆序对数目。] [朴素的算法时间复杂度是 O(n^2) 的。] [用归并排序求逆序对数可以通过本题。需要提醒的是，答案可能超过 32 位整数的范围哦。] [逆序对数目同样可以用树状数组优化朴素的 O(n^2) 算法，并获得和归并排序相同的时间复杂度。有兴趣的同学可以自行学习。] 代码 #include <iostream> #include<vector> #pragma warning(disable:4996) 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;//等价于mid=(l+r)/2 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;//统计产生逆序对数目(注意此处不能用cnt++,因为左边已经有序，此时若seq[q] < seq[p]说明seq[q]比seq[p]~seq[mid]都小 } } for (int i = l; i <= r; ++i) seq[i] = seqTemp[i];//将排序后的序列复制回原序列的对应位置 }
// 这个函数的功能是计算答案（即最少花费的金钱） // n：表示序列长度 // a：存储整个序列 a // 返回值：最少花费的金钱（需要注意，返回值的类型为 64 位有符号整数） long long getAnswer(int n) { /* 请在这里设计你的算法 */ seqTemp.resize(n);//初始化临时数组的长度，此算法需要额外的O(n)空间 cnt = 0;//置零计数器 mergeSort(0, n - 1);//进行归并排序 return cnt; }
// ================= 代码实现结束 =================
int main() { int n, tmp; seq.clear(); scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &tmp); seq.emplace_back(tmp); } long long ans = getAnswer(n); cout << ans << '\n'; return 0; } |