归并排序
归并排序相关知识点请见博客：信息奥赛｜归并排序🔗 / （备用）信息奥赛｜归并排序🔗
如链接失效，可以在文章末尾选择下一篇博客 或 在搜索界面搜索关键词「归并排序」即可。
题单 🧑🏻💻
| 题目来源 | 题目名称 | 题目链接 | 备注 | 难度 |
|---|---|---|---|---|
| 洛谷 - P1177 | 排序 | 链接🔗 | 归并排序模版题 | 🟢 |
| 洛谷 - P1908 | 逆序对 | 链接🔗 | 归并排序经典应用 | 🟢 |
| 信息学奥赛一本通 - 1328 | 光荣的梦想 | 链接🔗 | 归并排序经典应用 | 🟢 |
题解 🚀
归并排序
题目信息 📚
【题目名称】洛谷 P1177 - 排序
【题目描述】
将读入的 $N$ 个数从小到大归并排序后输出。
【输入】
第一行为一个正整数 $N$。
第二行包含 $N$ 个空格隔开的正整数 $a_i$，为你需要进行排序的数。
【输出】
将给定的 $N$ 个数从小到大输出，数之间空格隔开，行末换行且无空格。
【输入样例】
5
4 2 4 5 1【输出样例】
1 2 4 4 5【数据范围】
对于 $20%$ 的数据，有 $1 \leq N \leq 10^3$；
对于 $100%$ 的数据，有 $1 \leq N \leq 10^5$，$1 \le a_i \le 10^9$。
【原题链接】
https://www.luogu.com.cn/problem/P1177
题目解析 🍉
【题目分析】
归并排序の模版题（具体分析见「归并排序」知识点介绍博客：信息奥赛｜归并排序🔗 / （备用）信息奥赛｜归并排序🔗）
【C++ 代码】
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, a[N], tmp[N];
//归并排序
void msort(int l, int r) {
//递归条件，和快排相同
if (l >= r) return;
//归并排序先二分，再合并
int mid = l + r >> 1;
msort(l, mid);
msort(mid + 1, r);
//设置双指针i和j，分别遍历两个分好的有序序列，t为临时数组指针
int i = l, j = mid + 1, t = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) {
tmp[t++] = a[i++];
} else {
tmp[t++] = a[j++];
}
}
//若双指针未到末尾，把剩余元素添加至临时数组中
while (i <= mid) tmp[t++] = a[i++];
while (j <= r) tmp[t++] = a[j++];
//拷贝临时数组元素至原数组中
for (int i = l; i <= r; i++) a[i] = tmp[i];
}
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
msort(1, n); //归并排序
for (int i = 1; i <= n; i++) cout << a[i] << " ";
cout << endl;
return 0;
}逆序对
题目信息 📚
【题目名称】洛谷 P1908 - 逆序对
【题目描述】
猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。
最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 $a_i>a_j$ 且 $i<j$ 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。
【输入】
第一行，一个数 $n$，表示序列中有 $n$个数。
第二行 $n$ 个数，表示给定的序列。序列中每个数字不超过 $10^9$。
【输出】
输出序列中逆序对的数目。
【输入样例】
6
5 4 2 6 3 1【输出样例】
11【数据范围】
对于 $25%$ 的数据，$n \leq 2500$
对于 $50%$ 的数据，$n \leq 4 \times 10^4$。
对于所有数据，$n \leq 5 \times 10^5$
请使用较快的输入输出
【原题链接】
https://www.luogu.com.cn/problem/P1908
题目解析 🍉
【题目分析】
归并排序の经典应用（具体分析见「归并排序」知识点介绍博客：信息奥赛｜归并排序🔗 / （备用）信息奥赛｜归并排序🔗）
【C++ 代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
int n, a[N], t[N];
ll cnt; //逆序对的数量最多约为n^2，爆int
// 归并排序统计逆序对数量
void InversionCount(int l, int r) {
if (l >= r) return;
//归并排序递归调用
int mid = (l + r) / 2;
InversionCount(l, mid);
InversionCount(mid + 1, r);
//对已经有序的两个序列求逆序对数量
int p1 = l, p2 = mid + 1, p3 = l;
while (p1 <= mid && p2 <= r) {
if (a[p1] <= a[p2]) {
t[p3++] = a[p1++];
} else {
t[p3++] = a[p2++];
cnt = cnt + (mid - p1 + 1); //核心代码
}
}
while (p1 <= mid) t[p3++] = a[p1++];
while (p2 <= r) t[p3++] = a[p2++];
for (int i = l; i <= r; ++i) a[i] = t[i];
}
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
// 读入数据
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
// 归并排序统计逆序对数量
InversionCount(1, n);
cout << cnt << endl;
return 0;
}光荣的梦想
题目信息 📚
【题目名称】信息学奥赛一本通 1328 - 光荣的梦想
【题目描述】
Prince 对他在这片大陆上维护的秩序感到满意，于是决定启程离开艾泽拉斯。在他动身之前，Prince 决定赋予 King_Bette 最强大的能量以守护世界、保卫这里的平衡与和谐。在那个时代，平衡是个梦想。因为有很多奇异的物种拥有各种不稳定的能量，平衡瞬间即被打破。KB 决定求助于你，帮助他完成这个梦想。
一串数列即表示一个世界的状态。
平衡是指这串数列以升序排列。而从一串无序数列到有序数列需要通过交换数列中的元素来实现。KB 的能量只能交换相邻两个数字。他想知道他最少需要交换几次就能使数列有序。
【输入】
第一行为数列中数的个数 n。第二行为 n <= 10000 个数，表示当前数列的状态。
【输出】
输出一个整数，表示最少需要交换几次能达到平衡状态。
【输入样例】
4
2 1 4 3【输出样例】
2【题目链接】
http://ybt.ssoier.cn:8088/problem_show.php?pid=1328
题目解析 🍉
【题目分析】
经过分析，本题就是求一个序列的逆序对个数，故选择 归并排序求解逆序对 的模版即可。
【C++ 代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
int n, a[N], t[N];
ll cnt; //逆序对的数量最多约为n^2，爆int
// 归并排序统计逆序对数量
void InversionCount(int l, int r) {
if (l >= r) return;
//归并排序递归调用
int mid = (l + r) / 2;
InversionCount(l, mid);
InversionCount(mid + 1, r);
//对已经有序的两个序列求逆序对数量
int p1 = l, p2 = mid + 1, p3 = l;
while (p1 <= mid && p2 <= r) {
if (a[p1] <= a[p2]) {
t[p3++] = a[p1++];
} else {
t[p3++] = a[p2++];
cnt = cnt + (mid - p1 + 1); //核心代码
}
}
while (p1 <= mid) t[p3++] = a[p1++];
while (p2 <= r) t[p3++] = a[p2++];
for (int i = l; i <= r; ++i) a[i] = t[i];
}
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
// 读入数据
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
// 归并排序统计逆序对数量
InversionCount(1, n);
cout << cnt << endl;
return 0;
}参考资料 📚
信息学奥赛一本通 - http://ybt.ssoier.cn:8088/index.php
