火柴排队(逆序对 + 离散化)

news/2024/4/21 13:48:22/文章来源:https://blog.csdn.net/m0_72256122/article/details/136543015

505. 火柴排队

原题链接
在这里插入图片描述

思路

如下是画图分析的一些过程
在这里插入图片描述
在这里贪心的思路是排序,然后两个数组都是从小到大那样对应的话最终的答案可达到最小
而我们只能交换相邻的火柴,故在这里先假设一个简化版本,即A有序,而只需要对B进行操作,可发现,其实就是再在求逆序对数量在这里插入图片描述
有了简化版本思路,我们再对原数组进行处理,这里想到将其转化为简化版,也就是将原数组映射为排好序的1,2,3,…这样的数组,然后相应的也映射到B数组,随后就可以进行操作了
要注意的一点,数据过大,故先将a[], b[]数组进行离散化

离散化的话一般是从下标1开始的,故题目中最好也用下标从1开始

代码如下

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, MOD = 99999997;
int n, a[N], b[N], c[N], p[N];  //这里的p数组可理解为临时数组,用来当作容器为其他数组服务
//c[]数组为映射数组void work(int a[]) {for(int i = 1; i <= n; i++) p[i] = a[i];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;
}int merge_sort(int l, int r) {if(l >= r)  return 0;int mid = l + r >> 1;//这里的分治区间别忘了累加resint res = (merge_sort(l, mid) + merge_sort(mid + 1, r) ) % MOD;int i = l, j = mid + 1, k = 0;while(i <= mid && j <= r) {if(b[i] <= b[j])    p[k++] = b[i++];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(int i = l, j = 0; i <= r; 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);//然后,进行映射,将A数组映射为一个排好序的数组,B数组根据A数组数据也对应位置for(int i = 1; i <= n; i++) c[a[i]] = i;//对B的操作,在映射数组C[]中找b[i]的映射数据for(int i = 1; i <= n; i++) b[i] = c[b[i]];//最后,进行求最少交换次数(逆序对数量)int ans = merge_sort(1, n) % MOD;cout << ans;return 0;
}

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

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

相关文章

HTML+CSS+BootStrap游乐园官网

一、技术栈 支持pc、pad、手机访问&#xff0c;页面自适应&#xff01;&#xff01; html5cssbootstrapjs 二、项目截图 接受项目定制&#xff0c;站内联系博主&#xff01;&#xff01;&#xff01;

获取别人店铺的所有商品API接口

使用淘宝淘口令接口的步骤通常包括&#xff1a; 注册成为淘宝开放平台的开发者&#xff1a;在淘宝开放平台网站上注册账号并完成认证。 创建应用以获取API密钥&#xff1a;在您的开发者控制台中创建一个应用&#xff0c;并获取用于API调用的密钥&#xff0c;如Client ID和Clie…

机试指南:Ch5:线性数据结构 Ch6:递归与分治

文章目录 第5章 线性数据结构1.向量 vector2.队列 queue(1)队列的特点、应用(2)基本操作(3)例题例题1&#xff1a;约瑟夫问题2 &#xff08;难度&#xff1a;中等&#xff09; (4)习题习题1&#xff1a;排队打饭 &#xff08;难度&#xff1a;中等&#xff09; 3.栈 stack(1)栈…

【微前端】为什么需要微前端

1 什么是微前端 微前端就是将不同的功能按照不同的维度拆分成多个子应用。通过主应用来加载这些子应用。 微前端的核心在于拆&#xff0c;拆完后再合 2. 为什么去使用他 ○ 不同团队间开发同一个应用技术栈不同 ○ 希望每个团队都可以独立开发&#xff0c;独立部署 ○ 项目中…

mitmproxy代理

文章目录 mitmproxy1. 网络代理2. 安装3. Https请求3.1 启动mitmproxy3.2 获取证书3.3 配置代理3.4 运行测试 4. 请求4.1 读取请求4.2 修改请求4.3 拦截请求 5. 响应5.1 读取响应5.2 修改响应 6. 案例&#xff1a;共享账号6.1 登录bilibili获取cookies6.2 在代理请求中设置cook…

【单调栈】Leetcode 739.每日温度

【单调栈】Leetcode 739.每日温度 解法&#xff1a;维护单调栈栈中存的是数组的索引 解法&#xff1a;维护单调栈栈中存的是数组的索引 栈中存的是数组的索引 当新的值比当前栈顶的大&#xff0c;那么就执行出栈-更新result数组-判断当新的值比当前栈顶的大&#xff1f;的循环…

如何学习I2C协议

文章目录 学习I2C协议0 懒人直达1 了解协议开发者2 从恩智浦半导体公司下载官方技术文档3 翻译成中文4 资源下载 学习I2C协议 0 懒人直达 点击直达 1 了解协议开发者 I2C&#xff08;Inter-Integrated Circuit&#xff09;协议是由荷兰皇家飞利浦电子公司&#xff08;现恩智…

Unity Samples和帧动画的问题

拖动序列帧图片和自己创建clip的帧率不同 我今天在创建帧动画的时候用了两种方式第一种是直接拖动序列帧图片到Hierachy&#xff0c;然后生成的第二种是这样我发现两者播放的动画速率不一样最后查了半天查不到原因。最后发现是Samples的原因&#xff0c;而且Unity把Samples这个…

Python数据处理实战(4)-上万行log数据提取并作图进阶版

系列文章&#xff1a; 0、基本常用功能及其操作 1&#xff0c;20G文件&#xff0c;分类&#xff0c;放入不同文件&#xff0c;每个单独处理 2&#xff0c;数据的归类并处理 3&#xff0c;txt文件指定的数据处理并可视化作图 4&#xff0c;上万行log数据提取并作图进阶版&a…

外包干了5天,技术退步明显。。。。。

在湖南的一个安静角落&#xff0c;我&#xff0c;一个普通的大专生&#xff0c;开始了我的软件测试之旅。四年的外包生涯&#xff0c;让我在舒适区里逐渐失去了锐气&#xff0c;技术停滞不前&#xff0c;仿佛被时间遗忘。然而&#xff0c;生活的转机总是在不经意间降临。 与女…

别再盲目推广!用Xinstall精准追踪App下载渠道

在移动互联网时代&#xff0c;App推广已经成为企业获取用户、提升品牌知名度的重要手段。然而&#xff0c;面对众多的推广渠道和复杂的用户行为&#xff0c;如何精准统计App下载渠道来源&#xff0c;成为了广告主和开发者亟待解决的问题。今天&#xff0c;我们就来聊聊国内专业…

Go 互斥锁的实现原理?

Go sync包提供了两种锁类型&#xff1a;互斥锁sync.Mutex 和 读写互斥锁sync.RWMutex&#xff0c;都属于悲观锁。 概念 Mutex是互斥锁&#xff0c;当一个 goroutine 获得了锁后&#xff0c;其他 goroutine 不能获取锁&#xff08;只能存在一个写者或读者&#xff0c;不能同时…

docker 部署prometheus+grafana

首先进行部署docker 配置阿里云依赖&#xff1a; curl -o /etc/yum.repos.d/CentOS-Base.repo https://mirrors.aliyun.com/repo/Centos-7.repo # 配置centos 7的镜像源 yum install -y yum-utils device-mapper-persistent-data lvm2 # 安装一些后期或需要的的一下依…

[Java 探索之路~大数据篇] 新时代大数据流处理入门指南

本文主要介绍大数据基础&#xff0c;以及 flink 流计算 文章目录 【基础知识】1. 批处理与流处理1.批处理2.流处理 2. 为什么需要一个优秀的流处理框架1. 股票交易的业务场景2.生产者——消费者模型3. 流处理框架要解决的诸多问题&#xff08;1&#xff09;可扩展性&#xff08…

2024年腾讯云学生服务器优惠活动「云+校园」政策解读

2024年腾讯云学生服务器优惠活动「云校园」&#xff0c;学生服务器优惠价格&#xff1a;轻量应用服务器2核2G学生价30元3个月、58元6个月、112元一年&#xff0c;轻量应用服务器4核8G配置191.1元3个月、352.8元6个月、646.8元一年&#xff0c;CVM云服务器2核4G配置842.4元一年&…

【C++从0到王者】第五十一站:B+树

文章目录 一、B树1.B树的概念2.B树的特性3.B树的插入的过程4.总结 二、B*树1. B*树的概念2.B*树的分裂 三、总结四、B树系列和哈希和平衡搜索树作对比五、B树的一些应用1.索引2.MySQL索引3.MyISAM2.InnoDB 一、B树 1.B树的概念 B树是B树的变形&#xff0c;是在B树基础上优化的…

C++ 链表OJ

目录 1、2. 两数相加 2、24. 两两交换链表中的节点 3、143. 重排链表 4、23. 合并 K 个升序链表 5、25. K 个一组翻转链表 解决链表题目常用方法&#xff1a; 1、画图 2、引入虚拟"头”结点 便于处理边界情况方便我们对链表操作 3、大胆定义变量&#xff0c;减少连接…

2024-3-7 市场分歧视角

昨天安奈儿市场带领市场情绪一致&#xff0c;新型工业化方向独占鳌头&#xff0c;日内高潮节点尾盘老龙 克来机电涨停&#xff0c;昨晚很多老师在YY老龙是不是要二波了&#xff0c;呵呵。 今天市场分歧从竞价就开始了&#xff0c;隔夜单我记忆中 天奇股份88亿&#xff0c;上海…

python71-Python的函数入门,定义函数和调用函数

在使用函数之前必须先定义函数&#xff0c;定义函数的语法格式如下&#xff1a; def 函数名(形参列表)://由零条到多条可执行语句组成的函数[return [返回值]] Python声明函数必须使用def关键字&#xff0c;对函数语法格式的详细说明如下。 1&#xff09;函数名:从语法角度来…

力扣--从前序与中序遍历序列构造二叉树

题目&#xff1a; 思想&#xff1a; 首先先序遍历能确定根节点的值&#xff0c;此时查看该值在中序遍历中的位置&#xff08;如果索引为i&#xff09;&#xff0c;那么i左侧为左子树&#xff0c;i 右侧为右子树。从中序数组中即可看出左子树结点个数为 i&#xff0c;右子树节点…