文章目录
- 归并排序
- 例题
- 题意
- 分析
- 代码
归并排序
什么是归并排序？ 归并排序是复杂度为O(nlog(n))的排序算法，运用了分治法的思想，虽然一般直接使用sort()，不需要自己写排序，但归并排序的典型应用如 逆序对问题。
归并排序具体实现
- 分解 把序列分解成两个子序列，直到序列包含1个数，递归最底层。
- 求解子问题 由于最底层子序列只包含1个数，其实不用排序。
- 合并 归并两个有序子序列，如图二{1，7}和{2，3}，令i，j分别指向两个子序列第一个数进行比较，a[i]<a[j]，则把a[i]放到b[]中，依次类推比较得到b[]={1,2,3,7}
例题
传送门: HDU-4911
bobo has a sequence a 1,a 2,…,a n. He is allowed to swap two adjacent numbers for no more than k times. Find the minimum number of inversions after his swaps. Note: The number of inversions is the number of pair (i,j) where 1≤i<j≤n and a i>a j.
input:
The input consists of several tests. For each tests: The first line contains 2 integers n,k (1≤n≤10 5,0≤k≤10 9). The second line contains n integers a 1,a 2,…,a n (0≤a i≤10 9).
output:
For each tests: A single integer denotes the minimum number of inversions.
Sample Input:
代码语言：javascript复制3 1
2 2 1
3 0
2 2 1Sample Output:
代码语言：javascript复制1
2题意
交换任意相邻两个元素，不超过k次，求最少的逆序对。
分析
在归并排序合并子序列时，如果一个子序列比后面子序列的元素大，就会产生逆序对（如上图二(b)）,反之不会(图二(a))。产生的数量就是源码中的cnt =mid-i 1。求出逆序对数量cnt后，k次交换每次可以减少1个逆序对，即答案为cnt-k。 注意不超过k次，意思可以不一定要k次，就是cnt<=k时，输出0即可。
代码
代码语言：javascript复制#include<cstdio>
using namespace std;
typedef long long ll;
const int maxn = 100005;
ll n, k, cnt, a[maxn], b[maxn];
void Mergesort(ll l, ll r) {//归并排序
if (l >= r)return;
ll mid = (l r) / 2;//分成两个子序列
Mergesort(l, mid);
Mergesort(mid 1, r);
//合并
ll idx = 0, i = l, j = mid 1;
while (i <= mid && j <= r) {
if (a[i] > a[j]) {
b[idx ] = a[j ];
cnt = mid - i 1;//记录逆序对
}
else b[idx ] = a[i ];
}
while (i <= mid)b[idx ] = a[i ];
while (j <= r)b[idx ] = a[j ];
for (i = 0; i < idx; i )a[i l] = b[i];//写回原数组
}
int main() {
while (~scanf("%lld%lld", &n, &k)) {
cnt = 0;
for (ll i = 0; i < n; i )scanf("%lld", &a[i]);
Mergesort(0, n - 1);
if (cnt <= k)printf("0n");
else printf("%lldn", cnt - k);
}
return 0;
}原创不易，请勿转载（
本不富裕的访问量雪上加霜） 博主首页：https://blog.csdn.net/qq_45034708
