火柴排队.

题意:给两列火柴,可以交换任意相邻的火柴,使得(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;
}
相关文章:
火柴排队.
题意:给两列火柴,可以交换任意相邻的火柴,使得(ai-bi)^2的和最小,求最小交换次数。 分析:使得(ai-bi)^2的和最小,即a^2-2abb^2的和最小,那么使得2ab最大,就可…...
改善游戏体验:数据分析与可视化的威力
当今,电子游戏已经超越了娱乐,成为一种文化现象,汇聚了全球数十亿的玩家。游戏制作公司正采用越来越复杂的技术来提高游戏质量,同时游戏数据分析和可视化工具变得不可或缺。 数据的力量:解析游戏体验 游戏制作涉及到大…...
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 二叉搜索树中的搜索 给定二叉搜索树(BST)的根节点 root 和一个整数值 val。 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 null 。 示例 1: 输入:root [4,2,7,1,…...
【java学习—八】单例设计模式(5)
文章目录 1. 相关概念2. 单例设计模式-饿汉式3. 单例设计模式-懒汉式4. 总结 1. 相关概念 单例:只有一个实例(实例化对象) 设计模式是在大量的实践中总结和理论化之后优选的代码结构、编程风格、以及解决问题的思考方式。设计模式就像是经典的…...
【设计模式】第4节:创建型模式之“单例模式”
一、介绍 采取一定的方法保证在整个的软件系统中,对某个类只能存在一个对象实例,并且该类只提供一个取得其对象实例的方法。 不使用单例模式的UML类图: 使用单例模式的UML类图: 使用场景: 需要频繁创建或销毁的对象…...
NodeJS爬取墨刀上的设计图片
背景 设计人员分享了一个墨刀的原型图,但是给的是只读权限,无法下载其中的素材;开发时想下载里面的一张动图,通过浏览器的F12工具在页面结构找到了图片地址。 但是浏览器直接访问后发现没权限: Nginx 的 403 页面。。…...
linux--
一、crond 任务调度 1、原理示意图 2、crontab 进行定时任务的设置 2.1. 概述 任务调度,是指系统在某个时间执行的特定的命令或程序。任务调度分类: 系统工作: 有些重要的工作必须周而复始地执行。如病毒扫描等 个别用户工作:个别用户可能希望执行某些…...
conda虚拟环境笔记收录
1、安装conda 增加执行权限: chmod x Anaconda3-2023.03-1-Linux-x86_64.sh 开始执行:./Anaconda3-2023.03-1-Linux-x86_64.sh2、查看版本 conda --version3、查看当前虚拟环境 虚拟环境和全局环境有前缀可见 如果不进行设置,重新启动就变成…...
RGB-T Salient Object Detection via Fusing Multi-Level CNN Features
ADFC means ‘adjacent-depth feature combination’,MGF means ‘multi-branch group fusion’,JCSA means ‘joint channel-spatial attention’,JABMP means ‘joint attention guided bi-directional message passing’ 作者未提供代…...
安卓开发实例:方向传感器
调用手机的方向传感器,X轴,Y轴,Z轴的数值 activity_sensor.xml <?xml version"1.0" encoding"utf-8"?> <androidx.constraintlayout.widget.ConstraintLayoutxmlns:android"http://schemas.android.c…...
[论文笔记]GTE
引言 今天带来今年的一篇文本嵌入论文GTE, 中文题目是 多阶段对比学习的通用文本嵌入。 作者提出了GTE,一个使用对阶段对比学习的通用文本嵌入。使用对比学习在多个来源的混合数据集上训练了一个统一的文本嵌入模型,通过在无监督预训练阶段和有监督微调阶段显著增加训练数…...
Prometheus字段解析
官方文档::Configuration | Prometheus 1、全局配置指定在所有其他配置上下文中有效的参数。它们还用作其他配置部分的默认值。 global:# How frequently to scrape targets by default.默认情况下,定期抓取目标的频率是多久一次?…...
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,接受三个参数obj、setBind和getlogger。 // obj是需要进行监视的对象。 // setBind是一个回调函数,用于在设置属性时进行绑定操作。 // getlogger是一个回调函数,用于在获取属性时…...
实现寄生组合继承
寄生组合继承是一种继承方式,它通过组合使用构造函数继承和原型继承的方式,实现了高效而且正确的继承方式。 具体实现步骤如下: ① 定义一个父类,实现其属性和方法: function Person(name) {this.name namethis.age…...
ARM 账号注册报错 The claims exchange ‘Salesforce-UserWriteUsingEmail‘
ARM 账号注册报错 The claims exchange ‘Salesforce-UserWriteUsingEmail’ 参考:ARM 账号注册报错 The claims exchange ‘Salesforce-UserWriteUsingEmail’ specified in step ‘14’ returned HTTP error response with Code ‘BadRequest’ and Reason ‘Bad …...
笔记:电子设备接地,接的到底是什么地?
电路中有“地”,设备中有“地”;都是“地”,此地非彼地。 混淆的原因 有些混淆,是以为中文翻译造成的,英文所有Ground都统一翻译为“地”; 例1:英文Circuit Ground,应该翻译为电路…...
PY32F002A系列单片机:高性价比、低功耗,满足多样化应用需求
PY32F002A系列微控制器是一款高性能、低功耗的MCU,它采用32位ARM Cortex-M0内核,最高工作频率达到24MHz,提供了强大的计算能力。此外,PY32F002A拥有最大20Kbytes的flash存储器和3Kbytes的SRAM,为简单的数据处理提供了充…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
