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

本文主要是介绍【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 21 2 3 4 5
B 2 5 4 1 35 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)  //如果区间里只有一个数的话,就是0return 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 ++];elsep[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个数,映射到ifor (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

这篇关于【AcWing】蓝桥杯集训每日一题Day5|归并排序|离散化|二分|逆序数对|505.火柴排队(C++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/820209

相关文章

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时