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

Luogu P1966

题意简化

给定两个数组 \(a,b\),求让 \(\sum{(a_i-b_i)^2}\) 尽可能小所需要的最小交换次数

分析

首先,拆解题目给出的公式(完全平方)

\(\sum{(a_i-b_i)^2}=\sum {{a_i}^2+{b_i}^2-2a_ib_i}\)

可以发现,\(\sum{{a_i}^2+{b_i}^2}\) 是不会变的,那我们只能从 \(\sum 2a_ib_i\) 入手,让它尽可能大,答案就会尽可能小

那么易得,只要让大数和大数相乘,小数和小数相乘,\(a_i b_i\) 就会最大

所以只要将 \(a,b\) 排序就能得到最终序列

问题是我们求的是交换次数

那我们分析一下,其实要求的就是逆序对数量

使用树状数组即可

http://www.hskmm.com/?act=detail&tid=24452

相关文章:

  • 题解:P14036 [PAIO 2025] Rooks
  • 2025/8/26
  • 27 考研初试时间大约是什么时候?
  • 数据结构 - 跳表 Skip List
  • 06. 定时器
  • NOIP之前的复健记录
  • Linux 命令行安装达梦数据库
  • Google开源Tunix:JAX生态的LLM微调方案来了
  • 实用指南:Matlab通过GUI实现点云的快速全局配准(FGR)
  • 『OI 回忆录』停课有感
  • 『回忆录』初三第三学月
  • 完整教程:MySQL 5.7 主主复制 + Keepalived 高可用配置实例
  • 题解:P14074 [GESP202509 五级] 有趣的数字和
  • 解码Huffman 编码与 Huffman 树
  • 『回忆录』初三来高中的半学期
  • 10.1 容器云部署准备(一) - 实践
  • 关于缓冲区以及输出方式
  • 漏洞赏金计划的困境:i915漏洞与ChromeOS、Intel赏金项目剖析
  • RippleNet: Propagating User Preferences on the Knowledge Graph for Recommender Systems
  • 特地拎出来的总结
  • 2025异型件厂家推荐:邯郸市烁燊紧固件,广泛应用于建筑、桥梁、机械、电力、交通等诸多领域
  • Allow or block media autoplay in Firefox
  • [WC2018] 即时战略
  • 实用指南:Unity学习之C#的反射机制
  • HDF5文件 ——之三
  • 代码随想录算法训练营|Day 25
  • 深入解析:SAE J3072-2024插电式电动汽车(PEV)中的车载逆变器系统安全标准介绍
  • 冷僻模板整理
  • 实用指南:gitlab-runner 再次实践中理解和学习
  • 2025年7月28日当周关键漏洞汇总分析