火柴排队(c++实现)

题目


涵涵有两盒火柴,每盒装有 n 根火柴,每根火柴都有一个高度。

现在将每盒中的火柴各自排成一列,同一列火柴的高度互不相同,两列火柴之间的距离定义为:
∑i=1n(ai−bi)2

其中 ai 表示第一列火柴中第 i 个火柴的高度,bi 表示第二列火柴中第 i 个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。

请问得到这个最小的距离,最少需要交换多少次?

如果这个数字太大,请输出这个最小交换次数对 99,999,997 取模的结果。


输入


共三行,第一行包含一个整数 n,表示每盒中火柴的数目。

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

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


输出


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


样例


输入样例:
4
2 3 1 4
3 2 1 4


输出样例:
1


思路

首先我们可以假定a已经是升序排列的数组,然后如果我们想要让结果最小的话,b一定也要是升序的,所以我们可以转化为求逆序对的数量,首先我们定义几个数组,a,b不用解释了,然后第一步,我们把a数组中的每个元素,存在p中,p中存的是a中每个元素第几小,然后在把结果赋给a,b也是一样。为什么要这样,这样可以缩小a的范围,这样缩小并不对结果产生什么影响,因为结果主要考虑相对大小。总的来说,第一步就是缩小范围。
然后第二步
第二步首先在数组c中存放a[i],也就是说 a[i] 就是 c的下标。

c[a[i]] = i;

然后第三步
第三步就是 b 中存放 b[i] 在 c的位置 ,为什么要这么做,是因为,这么做就知道 b 和 a的相对位置了。为什么这么做b[i]一定有对应的a[i]?是因为 我们第一步就做了工作,此时a b 中存放的都是 相对位置,也就是第几小;
最后一步
就直接求b中逆序对的数量 就出来了

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, MOD = 99999997;

int n;
int a[N], b[N], c[N], p[N];

void work(int a[]){
    for(int i=0;i<n;i++) p[i] = i;
    
    sort(p,p+n,[&](int x,int y){
        return a[x]<a[y];
    });
    for(int i=0;i<n;i++) a[p[i]] = i;
}

int merge_sort(int l,int r){
    if(l>=r) return 0;
    int mid = l+r>>1;
    int 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(i=l,j=0;i<=r;i++,j++) b[i] = p[j];
    return res;
}


int main(){
    scanf("%d",&n);
    
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<n;i++) scanf("%d",&b[i]);
    
    work(a),work(b);
    for(int i=0;i<n;i++) c[a[i]] = i;
    for(int i=0;i<n;i++) b[i] = c[b[i]];
    
    int res = merge_sort(0,n-1);
    
    printf("%d",res);
}

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

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

相关文章

【OneAPI】贴纸生成API

OneAPI新接口发布&#xff1a;贴纸生成 生成一个10241024像素的贴纸。 API地址&#xff1a;POST https://oneapi.coderbox.cn/openapi/api/stickers 请求参数&#xff08;body&#xff09; 参数名类型必填含义说明prompt提示词是提示词示例&#xff1a;一只可爱的小狗 响应…

网络网络层之(1)IPv4地址

网络网络层之(1)IPv4地址 Author: Once Day Date: 2024年4月1日 一位热衷于Linux学习和开发的菜鸟&#xff0c;试图谱写一场冒险之旅&#xff0c;也许终点只是一场白日梦… 漫漫长路&#xff0c;有人对你微笑过嘛… 全系列文档可参考专栏&#xff1a;通信网络技术_Once-Day的…

嵌入式系统初学者指南

什么是嵌入式系统&#xff1f; 嵌入式系统是一种独立的、基于微处理器的计算机系统。您可以将其视为大型系统的一部分的微型计算机。如今&#xff0c;从洗碗机到波音 747&#xff0c;几乎所有“电子”产品内部都有嵌入式系统。但是&#xff0c;嵌入式系统与笔记本电脑或手机不…

mysql dublewrite 双写缓存机制

mysql dublewrite 双写缓存机制&#xff0c;像不像主板双bois系统&#xff0c; 在MySQL的InnoDB存储引擎中&#xff0c;当进行数据写操作时&#xff0c;会先将数据写入到内存中的缓冲池&#xff08;Buffer Pool&#xff09;&#xff0c;然后异步刷新到磁盘上的数据文件。为了提…

基于巴法云物联网云平台构建可视化控制网页(以控制LED为例)

0 前言 如今大大小小的物联网云平台非常多&#xff0c;但大部分要收取费用&#xff0c;免费的物联网云平台功能则有很多限制使用起来非常不方便。以百度云物联网云平台为例&#xff0c;它的物可视不支持发布主题&#xff0c;等于可视化界面只能作为数据监控而不具备双向通信的…

打造个人高效图床系统:威联通NAS+兰空+PicGo全方位整合教程

1.图床选择 最近因为家里人有使用图床的需求&#xff0c;又担心第三方图床跑路导致数据丢失&#xff0c;恰好家里有个威联通NAS&#xff0c;还有公网IP和域名&#xff0c;既然如此&#xff0c;那就动手自建一个图床吧&#xff0c;毕竟开源的图床应用还是有很多的。 一上来就在…

掌握数据相关性新利器:基于R、Python的Copula变量相关性分析及AI大模型应用探索

在工程、水文和金融等各学科的研究中&#xff0c;总是会遇到很多变量&#xff0c;研究这些相互纠缠的变量间的相关关系是各学科的研究的重点。虽然皮尔逊相关、秩相关等相关系数提供了变量间相关关系的粗略结果&#xff0c;但这些系数都存在着无法克服的困难。例如&#xff0c;…

写JDBC遇到的问题

执行会出现以下错误信息 java.sql.SQLSyntaxErrorException: You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near ? and loginPwd ? at line 1 at com.mysql.cj.jdbc.exceptions…

spark3.x新特性

Adaptive Query Execution自适应查询(SparkSQL) 由于缺乏或者不准确的数据统计信息&#xff08;元数据&#xff09;和对成本的错误估算&#xff08;执行计划调度&#xff09;导致生成的初始执行计划不理想 在Spark3.x版本提供Adaptive Query Execution自适应查询技术 通过在”…

数据结构顺序表的初始化,头插,尾插,头删,尾删,指定位置删除,指定位置插入,查找,销毁(详解)

目录 前言顺序表的介绍静态顺序表动态顺序表一.顺序表的初始化二.销毁扩容顺序表打印顺序表三.头插四.尾插五.头删六.尾删七.指定位置之前&#xff08;包括指定位置&#xff09;的插入八.指定位置数据的删除九.查找全部的代码实现总结 前言 数据结构是什么&#xff1f; 数据结…

碘浊度法与红外相机联用测定食品中维生素C

&#x1f31e;欢迎来到看论文的世界 &#x1f308;博客主页&#xff1a;卿云阁 &#x1f48c;欢迎关注&#x1f389;点赞&#x1f44d;收藏⭐️留言&#x1f4dd; &#x1f31f;本文由卿云阁原创&#xff01; &#x1f4c6;首发时间&#xff1a;&#x1f339;2024年4月6日&…

1.微服务

一、微服务是什么 微服务是一种架构风格&#xff0c;即&#xff0c;一个应用应该是一组小型服务&#xff0c;每个服务器只负责一种服务&#xff0c;服务之间可以通过 HTTP 的方式进行互通。每一个功能元素最终都是一个可独立替换和独立升级的软件单元。 可以说&#xff0c;微…

网络编程套接字应用分享【Linux C/C++ 】【UDP应用 | TCP应用 | TCP线程池小项目】

目录 前提知识 1. 理解源ip&#xff0c;目的ip和Macip 2. 端口号 3. 初识TCP&#xff0c;UDP协议 4. 网络字节序 5. socket 编程 sockaddr类型 一&#xff0c;基于udp协议编程 1. socket——创建套接字 2. bind——将套接字强绑定 3. recvfrom——接受数据 4. s…

c++11的重要特性2

可变参数模板在3中。 目录 ​编辑 1、统一的列表初始化&#xff1a; std::initializer_list&#xff1a; std::initializer_list是什么类型&#xff1a; std::initializer_list使用场景&#xff1a; 让模拟实现的vector也支持{}初始化和赋值 2、声明 auto decltype nul…

「每日跟读」英语常用句型公式 第4篇

「每日跟读」英语常用句型公式 第4篇 1. I’ve decided to ____ 我决定要____了 I’ve decided to take a vacation (我决定要去度假) I’ve decided to change my lifestyle (我决定要改变我的生活方式) I’ve decided to adopt a dog (我决定要收养一条狗了) I’ve dec…

【深度学习环境配置】一文弄懂cuda,cudnn,NVIDIA Driver version,cudatoolkit的关系

【深度学习环境配置】一文弄懂cuda&#xff0c;cuDNN&#xff0c;NVIDIA Driver version&#xff0c;cudatoolkit的关系 NVIDIA Driver version&#xff08;NVIDIA驱动程序&#xff09;CUDAcuDNNcudatoolkit深度学习环境配置顺序 今天突然发现配置的环境有些问题&#xff0c;意…

使用阿里云试用Elasticsearch学习:2.6 深入搜索——控制相关度

处理结构化数据&#xff08;比如&#xff1a;时间、数字、字符串、枚举&#xff09;的数据库&#xff0c;只需检查文档&#xff08;或关系数据库里的行&#xff09;是否与查询匹配。 布尔的是/非匹配是全文搜索的基础&#xff0c;但不止如此&#xff0c;我们还要知道每个文档与…

java日志框架简介

文章目录 概要常用日志框架常见框架有以下&#xff1a;slf4j StaticLoggerBinder绑定过程&#xff08;slf4j-api-1.7.32 &#xff09;JCL 运行时动态查找过程&#xff1a;&#xff08;commons-logging-1.2&#xff09;使用桥接修改具体日志实现 一行日志的打印过程开源框架日志…

【图论】【分类讨论】LeetCode3017按距离统计房屋对数目

本文涉及的知识点 图论 分类讨论 本题同解 【差分数组】【图论】【分类讨论】【整除以2】3017按距离统计房屋对数目 LeetCode3017按距离统计房屋对数目 给你三个 正整数 n 、x 和 y 。 在城市中&#xff0c;存在编号从 1 到 n 的房屋&#xff0c;由 n 条街道相连。对所有 …

服务效率飙升!2024最新Zoho Desk功能解析

2024年&#xff0c;立足于服务经济浪潮&#xff0c;如何为您的客户提供优质服务&#xff0c;高效解决客户工单&#xff0c;赢得客户美誉度&#xff0c;是当下各行企业的着力点。 在企业中&#xff0c;与客户发生最直接接触的就是客户服务部门。规范化客服部门业务流程&#xf…