【AcWing】蓝桥杯集训每日一题Day5|归并排序|离散化|二分|逆序数对|505.火柴排队(C++)

  1. 火柴排队
505. 火柴排队 - AcWing题库
难度:中等
时/空限制:1s / 128MB
总通过数:2058
总尝试数:4484
来源:NOIP2013提高组
算法标签
贪心离散化树状数组归并排序
题目内容

涵涵有两盒火柴,每盒装有 n 根火柴,每根火柴都有一个高度。
现在将每盒中的火柴各自排成一列,同一列火柴的高度互不相同,两列火柴之间的距离定义为:
∑ i = 1 n = ( a i − b i ) 2 \sum_{i=1}^{n}=(a_{i}-b_{i})^2 i=1n=(aibi)2
其中  a i a_{i} ai 表示第一列火柴中第i个火柴的高度, b i b_{i} bi 表示第二列火柴中第 i 个火柴的高度。 
每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。
请问得到这个最小的距离,最少需要交换多少次?
如果这个数字太大,请输出这个最小交换次数对 99,999,997 取模的结果。

输入格式

共三行,
第一行包含一个整数 n,表示每盒中火柴的数目。 
第二行有 n 个整数,每两个整数之间用一个空格隔开,表示第一列火柴的高度。
第三行有 n 个整数,每两个整数之间用一个空格隔开,表示第二列火柴的高度。

输出格式

输出共一行,包含一个整数,表示最少交换次数对99,999,997取模的结果。

数据范围

1 ≤ n ≤ 1 0 5 1\le n\le 10^5 1n105,
0 ≤ 火柴高度 ≤ 2 31 − 1 0\le火柴高度\le 2^{31}-1 0火柴高度2311

输入样例:
4
2 3 1 4
3 2 1 4
输出样例:
1
题目解析
  1. 有两盒火柴,每盒有n根,每根火柴都有一个高度
  2. 每一盒火柴内的高度各不相同
  3. 把两盒火柴排成一行,
    第一盒火柴用a来表示 a 1 , a 2 … a n a_{1},a_{2}\dots a_{n} a1,a2an
    第二盒火柴用b来表示 b 1 , b 2 … b n b_{1},b_{2}\dots b_{n} b1,b2bn
    所有的a都是互不相同的,所有的b也都是互不相同的
  4. 可以将所有相邻的火柴交换位置,两行火柴都可以交换
  5. 计算一下所有对应位置差的平方和,要让平方和最小的话,最少需要交换多少次

如果数字太大,输出次数对99999997取模的结果
数据范围是 1 0 5 10^5 105,所以时间复杂度需要控制在 O ( n log ⁡ n ) O(n\log n) O(nlogn)

考虑两个问题
  1. 什么情况下可以使和最小
  2. 如何通过最少的交换次数得到和最小的情况
问题一
不需要考虑顺序

距离只跟每两根火柴的对应关系有关
至于每根火柴在序列中的哪个位置是没有关系的

因此只需要考虑 a 1 a_{1} a1应该对应谁, a 2 a_{2} a2应该对应谁,以此类推
为了方便将a序列排序,因为a是不用考虑顺序的,第一问不需要考虑顺序
排成从小到大的结果

b也是升序排列的时候,平方和最小

再判断最小的数在最好的情况下应该对应哪个b,第二小的数应该对应哪个b,以此类推

可以猜一下,当b也是升序排列的时候,平方和最小
类似于排序不等式,但形式不完全一样
证明方式和排序不等式一样,和排队打水一样
913.排队打水

用反证法证明,假设b不是升序
必然存在 b i > b i + 1 b_{i}>b_{i+1} bi>bi+1,而 a i < a i + 1 a_{i}<a_{i+1} ai<ai+1
尝试交换这两个数
a i < a i + 1 a_{i}<a_{i+1} ai<ai+1
交换前 b i > b i + 1 b_{i}>b_{i+1} bi>bi+1
交换后 b i + 1 < b i b_{i+1}<b_{i} bi+1<bi

交换前后只影响 a i 和 a i + 1 a_{i}和a_{i+1} aiai+1这两列,不影响其他的列,所以其他列的和都是不变的
所以考虑交换前交换后的平方和的差异的话,只需要考虑这两列的差异就可以了

交换前的总和设为①,交换后的总和设②
比较关系可以做差,通过计算①-②,比较大小关系
①-② = ( a i − b i ) 2 + ( a i + 1 − b i + 1 ) 2 − ( a i − b i + 1 ) 2 − ( a i + 1 − b i ) 2 =(a_{i}-b_{i})^2+(a_{i+1}-b_{i+1})^2-(a_{i}-b_{i+1})^2-(a_{i+1}-b_{i})^2 =(aibi)2+(ai+1bi+1)2(aibi+1)2(ai+1bi)2
= 2 ( − a i b i − a i + 1 b i + 1 + a i b i + 1 + a i + 1 b i ) = 2 ( a i − a i + 1 ) ( b i + 1 − b i ) =2(-a_{i}b_{i}-a_{i+1}b_{i+1}+a_{i}b_{i+1}+a_{i+1}b_{i})=2(a_{i}-a_{i+1})(b_{i+1}-b_{i}) =2(aibiai+1bi+1+aibi+1+ai+1bi)=2(aiai+1)(bi+1bi)
最终的结果大于零,所以①大于②

所以交换前的总和大于交换后的总和
因此可以发现,如果存在一对逆序的话,(b如果不是升序,一定存在相邻的逆序),交换一下总和会变小,说明不是升序的话,就一定不是最优解


所以第一个问题,最小的a一定对应最小的b,第二小的a一定对应第二小的b,以此类推

问题二
需要考虑顺序

第二问就不能排序了,因为它只能交换相邻的火柴
比如
A 3 1 4 5 2
B 2 5 4 1 3
第一问不是真的排序,这是考虑a里面最小的1,在最优解里面应该对应哪个b

每个数的范围比较大,在 0 … 2 31 − 1 0\dots2^{31}-1 02311以内
后面因为要用这个数值当下标,数值比较大的话不容易做
但是这个问题是和这些数的绝对值是没有关系的,只和每个数的相对大小有关系,我们要把b调整成和a相对大小一样的序列,绝对值是没有影响的

离散化

做一个离散化,将序列映射成从1到n或者从0到n-1的连续自然数,这样做的好处是可以将值域可以从所有整数范围变到n以内
2.1 ∗ 1 0 9 → 1 0 5 2.1*10^{9}\to 10^5 2.1109105,这样就可以使用数组存了

离散化
802.区间和

离散化完之后,a数组变为1-n,b数组也变为1-n,
接下来要把a当中的1对应b当中的1,a当中的2对应b当中的2,以此类推
每次只能交换a当中相邻的两个数或者b里面相邻的两个数

考虑简化问题
  1. 假设输入的a是有序的
    A 1 2 3 4 5
    B 2 1 5 3 4
  2. 假设只能交换B
    如果把b变成和a一样的大小关系,a是升序的,所以要把b变成升序,最少需要交换几次
变成一个经典问题

给一个排列,问我们最少交换几次,每次交换相邻元素,把它变成一个升序
答案:逆序对数
看一下所有的元素对,不一定相邻,有多少个前一个大于后一个

为什么交换最少次数是逆序对

如果有序的话,逆序对应该是0
初始的时候,求一个逆序对,

2,1、
5,3、
5,4,

总共三个逆序对,每次交换两个相邻元素
比如交换x,y,每次交换xy之后对于逆序对的影响,如果逆序对数是k的话,只能让k+1或者-1,
如果x小于y的话,交换完,k+1
如果x大于y的话,交换完,k-1
交换xy的话,它不影响y跟前面的数的关系,也不影响x跟后面的数的关系,所以只会影响x跟y的关系,所以只会对逆序对数产生1的影响,要么+1,要么-1
最终要使逆序对变成零,所以最少需要操作3次
如果初始有k个逆序对的话,说明最少需要操作k次
所以答案一定大于等于k

可以等于k吗

可以,如果序列不是升序的话,必然存在一对相邻元素x,y,使得x大于y,交换这个相邻的逆序对就可以了,交换一次,k-1
因此只要k大于0,就必然可以找到一对相邻的前一个大于后一个,可以交换,必然可以使k-1
这样就可以构造一种方案,使得恰好操作k次,使得k变为0
所以等号可以取到

冒泡排序,每次交换就是会交换一对相邻的逆序对,冒泡排序就是一种方案

比如:2 1 5 3 4
由于不是升序,必然存在一对相邻的,前一个大于后一个
交换:1 2 5 3 4
5 3是一个
交换: 1 2 3 5 4
5 4是一个
交换: 1 2 3 4 5
三次

所以如果逆序对数是k的话,说明最少交换次数就是k

如何求逆序对数

经典问题

  1. 归并排序,递归的做法 O ( n log ⁡ n ) O(n\log n) O(nlogn)
    788.逆序对的数量

  2. 树状数组 O ( n log ⁡ n ) O(n\log n) O(nlogn)
    241.楼兰图腾

  3. 如果不止可以交换b,还可以交换a的话
    最优解是:
    因为a数组是升序的,逆序对数是0,b数组是k,
    不管交换a还是交换b,如果交换a的话,相当于是把a的逆序对数+1或者-1,交换b的话,相当于是把b的逆序对数+1或者-1.
    不管交换a还是交换b,a和b逆序对的差值,最多只能-1
    初始的时候逆序对的差值是k,所以最少需要操作k次,所以也是大于等于k
    所以如果不仅可以操作b,还可以操作a的话,跟只可以操作b是一样的

  4. 如果a没有序的话
    可以用映射的思想,因为a和b已经离散化了,它就是一个1~n的排列
    把a里面第一个数映射到1,把第二个数映射到2,以此类推,把a和b都映射一遍就好了

A 3 1 4 5 2
  1 2 3 4 5
B 2 5 4 1 3
  5 4 3 2 1

映射完之后,a就变成升序了,就变成了之前简化的问题
答案就是此时b序列当中的逆序对数

映射完之后把b变成升序,等价于把b映射之后的结果变成了1 2 3 4 5
这样a和b映射之后的结果都是1 2 3 4 5
根据映射可以反推回去,就直到交换完之后,原来的值
A 3 1 4 5 2
B 3 1 4 5 2
所以映射回去,就和原问题是一样的


a和b中的元素一定是一样的
因为离散化过
离散化之后,a和b都会变成1~n

为什么可以离散化
因为这个题只考虑相对关系,不考虑绝对关系

代码
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, MOD = 99999997;

int n;
int a[N], b[N], c[N], p[N];
//c存映射之后的数组,p是用来离散化的

void work(int a[])
{
	//把下标存下来,排下标就可以了
	for (int i = 1; i <= n; i ++)
		p[i] = i;
	//把p当作下标,根据下标在a当中对应的值来排
	sort (p + 1, p + n + 1, [&](int x, int y)
	{
		return a[x] < a[y];
	});
	//p就是下标,排完之后满足p有序,p作为下标的话,在a中有序

	//把a映射一下
	for (int i = 1; i <= n; i ++)
		a[p[i]] = i;
	//把a当中第二小的数映射到i
}

int merge_sort(int l, int r)
{
	if (l >= r)  //如果区间里只有一个数的话,就是0
		return 0;
	int mid = l + r >> 1;  //求一下中点
	//求一下左右两边的逆序对的总和
	int res = (merge_sort(1, mid) + merge_sort(mid + 1, r)) % MOD;
	//二类归并一下
	int i = 1, j = mid + 1, k = 0;
	while (i <= mid && j <= r)
	{
		if (b[i] < b[j])
			p[k ++] = b[j ++];
		else
			p[k ++] = b[j ++];
			res = (res + mid - i + 1) % MOD;
	}
	//把左边没有归并完的归并完
	while (i <= mid)
		p[k ++] = b[i ++];
	//把右边没有归并完的归并完
	while (j <= r)
		p[k ++] = b[j ++];
	//把临时数组中的元素存回原数组
	for (i = l, j = 0; j < k; i++, j++)
		b[i] = p[j];
	return res;
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++)
		scanf("%d", &a[i]);
	for (int i = 1; i <= n; i ++)
		scanf("%d", &b[i]);
	
	//先离散化一下
	work(a), work(b);

	//求一下c数组的映射
	for (int i = 1; i <= n; i ++)
		c[a[i]] = i;  //c当中第i个数,映射到i
	for (int i = 1; i <= n; i ++)
		b[i] = c[b[i]];  //要查一下b的数值映射的结果是什么

	//求一下b的逆序对数
	printf ("%d\n", merge_sort(1, n));
	return 0;
}

  1. 其中work函数里离散化p排序的时候
    排完之后
    a p 1 < a p 2 < ⋯ < a p n a_{p_{1}}<a_{p_{2}}<\dots<a_{p_{n}} ap1<ap2<<apn
    p 1 p_{1} p1存的是a里面最小的一个数的下标, p 2 p_{2} p2存的是第二小的数的下标

  2. 二分的写法

    1. 二分可以自己写
int find (int x)
{
	//在p这个升序里边,二分出来a第一次出现的位置
	int l = 1, r = n;
	while (l < r)
	{
		int mid = l + r >> 1;
		if (p[mid] >= x) r = mid;
		else l = mid + 1;
	}
	return r;
}

void work(int a[])
{
	//首先把a当中的数都存下来
	for (int i = 1; i <= n; i ++)
		p[i] = a[i];
	//把p排个序
	sort (p + 1, p + n + 1);
	//二分
	for (int i = 1; i <= n; i ++)
		a[i] = find (a[i]);
} 
2. 或者使用库函数
void work(int a[])
{
	//首先把a当中的数都存下来
	for (int i = 1; i <= n; i ++)
		p[i] = a[i];
	//把p排个序
	sort (p + 1, p + n + 1);
	//二分
	for (int i = 1; i <= n; i ++)
		a[i] = lower_bound(p + 1, p + n + 1, a[i]) - p;
} 
  1. 考虑一下怎么统计逆序数对
    merge_sort()函数中,左右两边归并
    ![[Pasted image 20240316155132.png]]

b[j]<b[i]的话,前半段所有大于b[j]的数应该是从i到mid
i前面的都是小于b[j]
i后面的都是大于b[j]
所以整个区间里面,前半段大于b[j]的数量,就是i~mid

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/461761.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于Pnpm + Turborepo + QianKun的微前端+Monorepo实践

基于Pnpm Turborepo QianKun的微前端Monorepo实践 背景 微前端一般都会涉及多个代码库&#xff0c;很多时候要一个一个代码库地去开发维护和运行&#xff0c;很不方便&#xff0c;这种时候引入Monorepo搭配微前端就能很好地解决这种问题&#xff0c;一个代码库就可以完成整…

AI赋能写作:AI大模型高效写作一本通

❤️作者主页&#xff1a;小虚竹 ❤️作者简介&#xff1a;大家好,我是小虚竹。2022年度博客之星评选TOP 10&#x1f3c6;&#xff0c;Java领域优质创作者&#x1f3c6;&#xff0c;CSDN博客专家&#x1f3c6;&#xff0c;华为云享专家&#x1f3c6;&#xff0c;掘金年度人气作…

文件包含例子

一、常见的文件包含函数 php中常见的文件包含函数有以下四种&#xff1a; include() require() include_once() require()_once() include与require基本是相同的&#xff0c;除了错误处理方面: include()&#xff0c;只生成警告&#xff08;E_WARNING&#xff09;&#x…

linux之source.list解析

众所周知&#xff0c;linux可以通过apt命令安装软件&#xff0c;那么apt又是从哪里获取软件包呢并安装呢&#xff1f;这里就绕不开一个文件source.list&#xff0c;该文件定义了软件源相关的信息。下面以实际例子&#xff0c;详细的介绍下这个文件。 文件作用 定义软件源的信…

MySQL-HMA 高可用故障切换

本章内容&#xff1a; 了解MySQL MHA搭建MySQL MHAMySQL MHA故障切换 1.案例分析 1.1.1案例概述 目前 MySQL 已经成为市场上主流数据库之一&#xff0c;考虑到业务的重要性&#xff0c;MySQL 数据库 单点问题已成为企业网站架构中最大的隐患。随着技术的发展&#xff0c;MHA…

【C++庖丁解牛】List容器的介绍及使用 | 深度剖析 | list与vector的对比

&#x1f341;你好&#xff0c;我是 RO-BERRY &#x1f4d7; 致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f384;感谢你的陪伴与支持 &#xff0c;故事既有了开头&#xff0c;就要画上一个完美的句号&#xff0c;让我们一起加油 目录 1. list的介绍1.1 list的…

每周一算法:双向深搜

题目描述 达达帮翰翰给女生送礼物&#xff0c;翰翰一共准备了 N N N 个礼物&#xff0c;其中第 i i i 个礼物的重量是 G [ i ] G[i] G[i]。 达达的力气很大&#xff0c;他一次可以搬动重量之和不超过 W W W的任意多个物品。 达达希望一次搬掉尽量重的一些物品&#xff0c;请…

冲动是魔鬼,工作不顺心时不要把坏脾气带给家人

今天与一个跟踪了很久的客户准备签合同了&#xff0c;客户突然反悔&#xff0c;为此与他周旋了一整天&#xff0c;忙碌得一口水都没有喝。回到小区坐在车里抽着烟&#xff0c;久久不愿回家&#xff0c;只想一个人坐着&#xff0c;疲惫、无奈。这个月的奖金似乎又将成为泡影。 …

mov格式视频怎么做二维码?视频在线做二维码的方法

如何将mov格式视频转二维码以后分享呢&#xff1f;视频二维码是现在手机获取视频内容很常用的一种方式&#xff0c;通过二维码生成器工具就可以快速在线生成二维码图片&#xff0c;使用手机扫码就可以播放视频。但是视频的格式有很多种&#xff0c;当我们需要将mov格式的视频生…

网络安全——关于防火墙

网络安全防火墙是很重要的部分&#xff0c;关于防火墙我们要知道&#xff0c;他默认所有流量都是黑名单&#xff0c;只有开启允许通过才可以。 我们通过一个实验来学防火墙命令。 防火墙要登录才能使用&#xff0c;用户名是admin,默认密码是Admin123&#xff0c;在第一次登录…

Spring AI Chat 简单示例

官方文档地址&#xff1a; https://docs.spring.io/spring-ai/reference/index.html Spring AI 可以方便 Java 开发者在代码中集成 AI 的功能&#xff0c;通过 Spring 提供的抽象&#xff0c;可以方便的切换不同的AI提供商&#xff0c;Spring AI 是对 AI 的使用&#xff0c;并…

Android 地图SDK 绘制点 删除 指定

问题 Android 地图SDK 删除指定绘制点 详细问题 笔者进行Android 项目开发&#xff0c;对于已标记的绘制点&#xff0c;提供撤回按钮&#xff0c;即删除绘制点&#xff0c;如何实现。 解决方案 新增绘制点 private List<Marker> markerList new ArrayList<>…

没有公式,不要代码,让你理解 RCNN:目标检测中的区域卷积神经网络

⭐️ 导言 在计算机视觉领域&#xff0c;目标检测是一项关键任务&#xff0c;它涉及识别图像中感兴趣的物体&#xff0c;并定位它们的位置。而RCNN&#xff08;Region-based Convolutional Neural Network&#xff09;是一种经典的目标检测算法&#xff0c;它以区域为基础进行…

BMP280 arduino调试

终于成功了。 #include <SPI.h> //定义数据类型 #define s32_t long signed int #define u32_t long unsigned int #define u16_t unsigned short #define s16_t signed short // 定义从设备选择引脚 const int chipSelectPin 10; //定义BMP280寄存器/// unsigned int …

R语言:如何基于地球外辐射(Ra)和相对日照(n/N)计算太阳辐射Rs?

正在编写相关软著&#xff0c;借此机会了解R语言的基本语法和一些处理流程&#xff0c;所以解释稍微繁琐。 Note&#xff1a; 使用的R语言版本是 R version 4.3.2 (2023-10-31 ucrt) 使用的RStudio编辑器版本是&#xff1a; 01 基于随机森林的插值填补缺失值 这是目前处理…

电子供应链的未来:电子元器件采购商城的洞察

电子供应链的未来将受到数字化技术、智能化制造和全球化贸易等趋势的深刻影响。在这一背景下&#xff0c;电子元器件采购商城将发挥越来越重要的作用&#xff0c;并提供以下洞察&#xff1a; 数字化转型&#xff1a; 电子元器件采购商城将更加注重数字化转型&#xff0c;通过引…

【计算机系统结构】重叠方式

&#x1f4dd;本文介绍 本文主要内容位计算机系统结构的重叠方式 &#x1f44b;作者简介&#xff1a;一个正在积极探索的本科生 &#x1f4f1;联系方式&#xff1a;943641266(QQ) &#x1f6aa;Github地址&#xff1a;https://github.com/sankexilianhua &#x1f511;Gitee地址…

不可变集合

2. 3. 如果键值对超过10个的话 优化之后 要生成不可变的集合直接使用copyof就可以

Python XML处理实战指南:从基础到高级技巧

Python XML处理实战指南&#xff1a;从基础到高级技巧 介绍XML基础XML的定义和特点XML结构组成命名空间&#xff08;Namespaces&#xff09;小结 Python中处理XML的库ElementTreeminidomlxml 使用ElementTree解析XML读取XML文件遍历XML元素查找特定元素修改XML文件 使用lxml处理…

除了「au revoir」,「再见」还能怎么说?柯桥成人学外语来银泰附近

1. Je dois y alle#15857575376r I have to go there Y there&#xff0c;意思是“我要走了”。 例如&#xff0c;”Moi, je dois y aller.” 对不起&#xff0c;我该走了。 如果你和同伴都要离开&#xff0c;那就可以说"On y va"&#xff0c;它相当于英语里…