归并排序详解 -HDU4911 Inversion(逆序对)

本是古典何须时尚 2023-03-13 11:40 6阅读 0赞

### 文章目录 ###

*  归并排序
 *  例题
 *   *  题意
     *  分析
     *  代码

# 归并排序 #

--------------------

**什么是归并排序？**  
归并排序是复杂度为O(nlog(n))的排序算法，运用了分治法的思想，虽然一般直接使用sort()，不需要自己写排序，但归并排序的典型应用如 逆序对问题。

**归并排序具体实现**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center]

*  分解  
    把序列分解成两个子序列，直到序列包含1个数，递归最底层。
 *  求解子问题  
    由于最底层子序列只包含1个数，其实不用排序。
 *  合并  
    归并两个有序子序列，如图二\{1，7\}和\{2，3\}，令i，j分别指向两个子序列第一个数进行比较，a\[i\]<a\[j\]，则把a\[i\]放到b\[\]中，依次类推比较得到b\[\]=\{1,2,3,7\}  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center 1]

# 例题 #

--------------------

传送门: [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:**

3 1
    2 2 1
    3 0
    2 2 1

**Sample Output:**

1
    2

## 题意 ##

交换任意相邻两个元素，不超过k次，求最少的逆序对。

## 分析 ##

在归并排序合并子序列时，如果一个子序列比后面子序列的元素大，就会产生逆序对（如上图二(b)）,反之不会(图二(a))。产生的数量就是源码中的cnt+=mid-i+1。求出逆序对数量cnt后，k次交换每次可以减少1个逆序对，即答案为cnt-k。  
注意不超过k次，意思可以不一定要k次，就是cnt<=k时，输出0即可。

## 代码 ##

#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("0\n");
    		else printf("%lld\n", cnt - k);
    	}
    	return 0;
    }

> **原创不易，请勿转载**（本不富裕的访问量雪上加霜 ）  
> 博主首页：[https://blog.csdn.net/qq\_45034708][https_blog.csdn.net_qq_45034708]  
> *如果文章对你有帮助，记得关注点赞收藏❤*

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center]: /images/20230312/4ab03c0fd8e34fc1a5fa4370cbf3f2cc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200513115508459.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4,size_16,color_FFFFFF,t_70#pic_center
[HDU-4911]: http://acm.hdu.edu.cn/showproblem.php?pid=4911
[https_blog.csdn.net_qq_45034708]: https://blog.csdn.net/qq_45034708