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

CF1439C Greedy Shopping

CF1439C Greedy Shopping


给定一个长为 \(n\)单调不增的数组 \(a\),有 \(q\) 次操作:

    1. 给出 \(x,y\),令区间 \([1,x]\) 内的数对 \(y\)\(\max\)
    1. 给出 \(x,y\),从左到右遍历 \([x,n]\) 内的每个数,如果 \(a_i\le y\),那么令 \(y\leftarrow y-a_i\),你需要回答这个过程中 \(y\) 被减了几次。

\[n,q\le 2\times 10^5\\ a_i,y\le 10^9 \]


首先有一个重要观察:至多有 \(\log y\) 段连续的数被 \(y\) 减去。

证明如下:

考虑相邻的两个数 \(a,b\),满足 \(y\ge a\),但是 \(y-a < b\),这个时候 \(a\) 会成为一个连续操作段的结尾。

由于 \(b\le a\),所以 \(y-a < a\),即 \(y < 2a\),那么有,

\[y-a < y-\dfrac y2 = \dfrac y2 \]

所以在这个过程中 \(y\) 至少会减少一半。那么显然最多只有 \(\log_2 y\) 段。


有了这个性质,我们就可以通过线段树简单维护来支持 \(\mathcal O(\log n)\) 处理一段连续的操作。

那么总时间复杂度: \(\mathcal O(q\log n\log V)\),其中 \(V\) 为值域。

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

相关文章:

  • 完整教程:AI应用生成平台:数据库、缓存与存储
  • CCPC2022绵阳 游记(VP)
  • 2025 年电缆桥架生产厂家最新推荐排行榜:含北方 / 河北 / 瓦楞 / 防火 / 模压 / 镀锌桥架品牌及合作案例盘点
  • 2025 年胰岛素泵厂家最新推荐排行榜:国产实力厂家技术、口碑及全场景适配方案全景解析软针植入/平衡式留置针/无异物感胰岛素泵厂家推荐
  • 2025 年国内磨床厂家最新推荐榜:聚焦平面磨床外圆磨床等品类,助力企业精准选优质设备
  • 2025 年加工中心厂家最新推荐榜:覆盖立式、卧式、龙门及 850 等多规格设备,帮采购方高效选实力厂商
  • 进程的内存管理
  • 深入理解Java内存模型与volatile关键字:从理论到实践
  • 完整教程:【stm32】cube固件解析和放入工程(HAL_F4)
  • 312、金缕衣
  • 使用 Visual Studio 快速创建 NuGet 程序包并发布到 NuGet 官网
  • 反配容斥
  • 怎么激活win11?笔记本重装系统后怎么激活Windows?
  • AVG Clear:彻底卸载AVG产品的专业工具
  • 现代 PHP8+ 实战特性介绍 Enums、Fibers 和 Attributes
  • php 1026
  • 用【WPF+Dlib68】实现 侧脸 眼镜虚拟佩戴 - 用平面图表现空间视觉 - 行人-
  • 科学背景如何赋能云计算业务战略
  • 【GitHub每日速递 251016】23k star,Daytona:90ms内极速运行AI代码,安全弹性基础设施来袭!
  • 用 【C# + Winform + Dlib68点】 实现静图眼镜虚拟佩戴 - 行人-
  • 图神经网络前沿技术与应用探索
  • MVCC、幻读、间隙锁与临键锁(三)
  • MVCC、幻读、间隙锁与临键锁
  • MVCC、幻读、间隙锁与临键锁(二)
  • 读AI赋能01超级能动性
  • 生物聚酯塑料回收技术创新与商业应用
  • 189 轮转数组 - MKT
  • SGD 到 AdamW 优化器的实践选型指南
  • 图文并茂展示CSS li 排版大合集,总有一款是你刚好需要的
  • 10.15 闲话