当前位置: 首页 > news >正文

火柴排队.

 题意:给两列火柴,可以交换任意相邻的火柴,使得(ai-bi)^2的和最小,求最小交换次数。

分析:使得(ai-bi)^2的和最小,即a^2-2ab+b^2的和最小,那么使得2ab最大,就可以使得整体最小。我们可以假设当序列有序时候,2ab最大。

假如a>b,c>d  ,那么ac+bd>ad+bc;

反证法:令ac+bd<ad+bc,那么c(a-b)<d(a-b),得出c<d,与事实不符,所以结论错误,即ac+bd>ad+bc,当序列有序时候,2ab最大。

此时问题就可以变为当序列有序时候,最小的交换次数怎么求

显然,把两个序列都从小到大,或者从大到小排列,显然交换次数不是最小的。

那么,可以求  a相对于b,把a排成和b大小关系一一对应的序列,即a序列的第一小和b序列的第一小在同一位置上,这样的交换次数是最少的。只需要 a队伍中第 i个数和 b队伍中第 i个数一一对应,那么就算两个队伍不是有序的也不影响结果。

所以我们可以存一下a,b序列的下标和数值,进行一下按值排序,就可以得到a,b的相对位置,此时可以增加一个数组c,c的下标存a数组的下标,c数组的值存b数组的下标,因为c数组下标是有序的,那么我们只要想到怎么使c数组的数值排序,使得数值也变成有序的就可以得到答案。

此时数值变成有序后,就表示a数组和b数组的大小关系变成了一一对应。

怎样变换可以想到树状数组或者逆序对。

#include<bits/stdc++.h>using namespace std;const int N = 1e5 + 10 , mod=99999997;
int n;
struct node
{int v,p;bool operator < (const node &w) const{return v<w.v;} 
}a[N],b[N];int tr[N];
int c[N];int lowbit(int x) 
{return x&(-x);
}
int query(int x)
{int res=0;for(int i=x;i>=1;i-=lowbit(i)) res+=tr[i];return res; 
}
void modify(int x,int c)
{for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=1;
}int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i].v,a[i].p=i;for(int i=1;i<=n;i++) cin>>b[i].v,b[i].p=i;sort(a+1,a+n+1);sort(b+1,b+n+1);for(int i=1;i<=n;i++)  c[a[i].p]=b[i].p;int res=0;for(int i=n;i>=1;i--){res = (res+query(c[i]))%mod;modify(c[i],1);}cout<<res<<endl;return 0;
}

相关文章:

火柴排队.

题意&#xff1a;给两列火柴&#xff0c;可以交换任意相邻的火柴&#xff0c;使得&#xff08;ai-bi)^2的和最小&#xff0c;求最小交换次数。 分析&#xff1a;使得&#xff08;ai-bi)^2的和最小&#xff0c;即a^2-2abb^2的和最小&#xff0c;那么使得2ab最大&#xff0c;就可…...

改善游戏体验:数据分析与可视化的威力

当今&#xff0c;电子游戏已经超越了娱乐&#xff0c;成为一种文化现象&#xff0c;汇聚了全球数十亿的玩家。游戏制作公司正采用越来越复杂的技术来提高游戏质量&#xff0c;同时游戏数据分析和可视化工具变得不可或缺。 数据的力量&#xff1a;解析游戏体验 游戏制作涉及到大…...

GEE:本地影像上传到GEE的Assets中,并输入机器学习算法中作为特征变量

作者:CSDN @ _养乐多_ 当我们在 Google Earth Engine(GEE)中应用机器学习算法时,会输入一些影像作为特征变量数据,进一步根据这些特征影像去推理未知区域的数据。但是 GEE 平台上计算特征变量的 API 函数并不是非常全面,我们希望获得更多的特征用于分类。这个时候,我们…...

【Mybatis源码】XMLConfigBuilder构建器 - 读取XML配置初始化Configuration对象

XMLConfigBuilder是Mybatis中定义的进行构建Configuration对象的类,此类用于读取XML配置文件创建并初始化Configuration对象; 上一篇中我们介绍了XMLConfigBuilder构建器加载XML配置文件以及创建Configuration对象https://blog.csdn.net/m1729339749/article/details/133983…...

Python算法练习 10.28

leetcode 700 二叉搜索树中的搜索 给定二叉搜索树&#xff08;BST&#xff09;的根节点 root 和一个整数值 val。 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在&#xff0c;则返回 null 。 示例 1: 输入&#xff1a;root [4,2,7,1,…...

【java学习—八】单例设计模式(5)

文章目录 1. 相关概念2. 单例设计模式-饿汉式3. 单例设计模式-懒汉式4. 总结 1. 相关概念 单例&#xff1a;只有一个实例&#xff08;实例化对象&#xff09; 设计模式是在大量的实践中总结和理论化之后优选的代码结构、编程风格、以及解决问题的思考方式。设计模式就像是经典的…...

【设计模式】第4节:创建型模式之“单例模式”

一、介绍 采取一定的方法保证在整个的软件系统中&#xff0c;对某个类只能存在一个对象实例&#xff0c;并且该类只提供一个取得其对象实例的方法。 不使用单例模式的UML类图&#xff1a; 使用单例模式的UML类图&#xff1a; 使用场景&#xff1a; 需要频繁创建或销毁的对象…...

NodeJS爬取墨刀上的设计图片

背景 设计人员分享了一个墨刀的原型图&#xff0c;但是给的是只读权限&#xff0c;无法下载其中的素材&#xff1b;开发时想下载里面的一张动图&#xff0c;通过浏览器的F12工具在页面结构找到了图片地址。 但是浏览器直接访问后发现没权限&#xff1a; Nginx 的 403 页面。。…...

linux--

一、crond 任务调度 1、原理示意图 2、crontab 进行定时任务的设置 2.1. 概述 任务调度&#xff0c;是指系统在某个时间执行的特定的命令或程序。任务调度分类&#xff1a; 系统工作: 有些重要的工作必须周而复始地执行。如病毒扫描等 个别用户工作:个别用户可能希望执行某些…...

conda虚拟环境笔记收录

1、安装conda 增加执行权限&#xff1a; chmod x Anaconda3-2023.03-1-Linux-x86_64.sh 开始执行&#xff1a;./Anaconda3-2023.03-1-Linux-x86_64.sh2、查看版本 conda --version3、查看当前虚拟环境 虚拟环境和全局环境有前缀可见 如果不进行设置&#xff0c;重新启动就变成…...

RGB-T Salient Object Detection via Fusing Multi-Level CNN Features

ADFC means ‘adjacent-depth feature combination’&#xff0c;MGF means ‘multi-branch group fusion’&#xff0c;JCSA means ‘joint channel-spatial attention’&#xff0c;JABMP means ‘joint attention guided bi-directional message passing’ 作者未提供代…...

安卓开发实例:方向传感器

调用手机的方向传感器&#xff0c;X轴&#xff0c;Y轴&#xff0c;Z轴的数值 activity_sensor.xml <?xml version"1.0" encoding"utf-8"?> <androidx.constraintlayout.widget.ConstraintLayoutxmlns:android"http://schemas.android.c…...

[论文笔记]GTE

引言 今天带来今年的一篇文本嵌入论文GTE, 中文题目是 多阶段对比学习的通用文本嵌入。 作者提出了GTE,一个使用对阶段对比学习的通用文本嵌入。使用对比学习在多个来源的混合数据集上训练了一个统一的文本嵌入模型,通过在无监督预训练阶段和有监督微调阶段显著增加训练数…...

Prometheus字段解析

官方文档&#xff1a;&#xff1a;Configuration | Prometheus 1、全局配置指定在所有其他配置上下文中有效的参数。它们还用作其他配置部分的默认值。 global:# How frequently to scrape targets by default.默认情况下&#xff0c;定期抓取目标的频率是多久一次&#xff1f;…...

msigdbr hallmarks gsea broad研究所

使用msigdbr r包 #BiocManager::install("msigdb") #https://www.gsea-msigdb.org/gsea/msigdb #https://cran.r-project.org/web/packages/msigdbr/vignettes/msigdbr-intro.html #https://bioconductor.org/packages/release/data/experiment/vignettes/msigdb/ins…...

理解V3中的proxy和reflect

现有如下面试题 结合GeexCode和Gpt // 这个函数名为onWatch&#xff0c;接受三个参数obj、setBind和getlogger。 // obj是需要进行监视的对象。 // setBind是一个回调函数&#xff0c;用于在设置属性时进行绑定操作。 // getlogger是一个回调函数&#xff0c;用于在获取属性时…...

实现寄生组合继承

寄生组合继承是一种继承方式&#xff0c;它通过组合使用构造函数继承和原型继承的方式&#xff0c;实现了高效而且正确的继承方式。 具体实现步骤如下&#xff1a; ① 定义一个父类&#xff0c;实现其属性和方法&#xff1a; function Person(name) {this.name namethis.age…...

ARM 账号注册报错 The claims exchange ‘Salesforce-UserWriteUsingEmail‘

ARM 账号注册报错 The claims exchange ‘Salesforce-UserWriteUsingEmail’ 参考&#xff1a;ARM 账号注册报错 The claims exchange ‘Salesforce-UserWriteUsingEmail’ specified in step ‘14’ returned HTTP error response with Code ‘BadRequest’ and Reason ‘Bad …...

笔记:电子设备接地,接的到底是什么地?

电路中有“地”&#xff0c;设备中有“地”&#xff1b;都是“地”&#xff0c;此地非彼地。 混淆的原因 有些混淆&#xff0c;是以为中文翻译造成的&#xff0c;英文所有Ground都统一翻译为“地”&#xff1b; 例1&#xff1a;英文Circuit Ground&#xff0c;应该翻译为电路…...

PY32F002A系列单片机:高性价比、低功耗,满足多样化应用需求

PY32F002A系列微控制器是一款高性能、低功耗的MCU&#xff0c;它采用32位ARM Cortex-M0内核&#xff0c;最高工作频率达到24MHz&#xff0c;提供了强大的计算能力。此外&#xff0c;PY32F002A拥有最大20Kbytes的flash存储器和3Kbytes的SRAM&#xff0c;为简单的数据处理提供了充…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...