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

鲜花 10.4:【半 whk 向】临项交换法贪心

题源:青岛 58 中高一作业。新定义能这么出?

直接考虑(3),这是一个经典问题 [NOIP 2012 提高组] 国王游戏 的模型,即临项交换法贪心。

题意即重排一个给定的二元组序列,使得 \(\max_{i=1}^n f_i\) 最小,其中, \(f_i = \sum_{k=1}^{i-1}(h_k-s_i)\)

考虑重排序列的过程本质上是在进行若干次相邻两项的交换,即类似冒泡排序的过程。

不妨令 \(j = i + 1\),记 \(sum_i = \sum_{k=1}^i h_k\),则交换前:

\[\begin{aligned} f_i &= sum_{i-1}-s_i \\ f_j &= sum_i-s_j=sum_{i-1}+h_i-s_j \end{aligned} \]

交换 \(i, j\),记现在 \(i,j\) 位置上的 \(f\) 值为 \(f_i',f_j'\),则:

\[\begin{aligned} f_i' &= sum_{i-1} - s_j\\ f_j' &= sum_{i - 1} + h_j - s_i \end{aligned} \]

答案只与最大的一项有关,所以我们要让较大的项尽可能小。所以当且仅当 \(sum_{i-1}+h_j-s_i<sum_{i-1}+h_i-s_j\) 时,交换是更优的。

整理,即:\(h_j+s_j<h_i+s_i\) 时,交换是更优的。

所以,我们按照 \(h_i+s_i\) 从小到大排序即可,特别注意的是,在此题中的不等号具有传递性,这是我们从邻项推广到整个序列的前提,不满足的典型例题是 皇后游戏,复习到的时候会写一下。

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

相关文章:

  • 前端学习教程-Pinia 教程
  • 布谷娱乐直播架构源码开发实用功能:技术驱动更迭的创新体验
  • Bean生命周期
  • 回忆QQ空间有感
  • mtgsig
  • 前端学习教程-Vue Router 教程
  • 详细介绍:Java-Spring 入门指南(十七)SpringMVC--Apipostl与RestFul实战测试
  • 详细介绍:告别 403 Forbidden!详解爬虫如何模拟浏览器头部(User-Agent)
  • 通过学习分位数函数提升预测准确性
  • 高中数列梳理
  • AtCoder Beginner Contest 426 实况记录 + A-D 题解
  • 提示词攻击如何防范(2025):从 Indirect Prompt Injection 到 RAG 供应链的分层防御实战
  • 【STM32项目开源】基于STM32的智能养殖场环境监测系统 - 详解
  • 前端学习教程-Axios
  • 『回忆录』返校前夜 230102
  • 断更
  • 前端学习教程-环境配置
  • TypeScript - Ref
  • 20251004 qmd 弱化规约(未完成)
  • 深入解析:人工智能专业术语详解(C)
  • 2025.10.4模拟赛
  • 黄金替罪羊
  • P5301 [GXOI/GZOI2019] 宝牌一大堆
  • 10.4 2025多校冲刺CSP模拟赛2 改题记录
  • 【比赛记录】2025CSP-S模拟赛58
  • 回忆有感
  • 框架高效的系统的演进如何塑造人工智能的深层语义分析能力
  • 『回忆录』高二上第一次月考——压力下的崛起,意料外的突破
  • AutoCAD 2025安装包下载 CAD免费下载 永久免费激活 附详细安装教程
  • 微分和积分的区别