当前位置: 首页 > 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;为简单的数据处理提供了充…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...