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

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...