专栏首页blog(为什么会重名,真的醉了)归并排序详解 -HDU4911 Inversion(逆序对)

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

文章目录

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

归并排序


什么是归并排序? 归并排序是复杂度为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:

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数论-同余与逆元

    将一个数拆成若干数,求其乘积最大。 先上结论:一个数n拆成m个数使其乘积最大,则拆成m个n/m;如果nm不整除则拆成一段连续自然数(从2开始,剩下的往前摊);...

    唔仄lo咚锵
  • 数论-快速幂、矩阵快速幂

    唔仄lo咚锵
  • Redis-性能测试(redis-benchmark)

    redis-benchmark是官方自带的性能测试工具,我们可以设置相关参数进行性能测试。

    唔仄lo咚锵
  • redis清空数据

    redis清空 

    似水的流年
  • LeetCode 434. 字符串中的单词数

    Michael阿明
  • SmartGit:Git版本控制系统的图形化客户端程序

    Git最初是一个由林纳斯·托瓦兹为了更好地管理linux内核开发而创立的分布式版本控制/软件配置管理软件。后来Git内核已经成熟到可以独立地用作版本控制。很多有...

    张善友
  • Android Monkey压力测试介绍

    Monkey 是Android SDK提供的一个命令行工具, 可以简单,方便地运行在任何版本的Android模拟器和实体设备上。 Monkey会发送伪随机的用户...

    测试开发社区
  • 2019 年互联网人才招聘报告:Java 吃香,算法工程师紧缺!

    在这篇文章中,我们将对 7 月份国内各个主流招聘网站发布的 384,0533 条互联网招聘需求进行全面分析。

    老九君
  • 致敬Vue3: 1.1万字从零解读Vue3.0源码响应式系统

    原文地址:https://hkc452.github.io/slamdunk-the-vue3/

    胡哥有话说
  • [Python分析]一线城市的房租在工资中占比高吗?

    在这个案例中,作者从网上公开信息中获取了不同城市的租房价格和工资水平,对数据进行整理之后,对比分析了不同条件下房租占工资的比重。

    Crossin先生

扫码关注云+社区

领取腾讯云代金券