CF1003D: Coins and Queries

硬币面值都是 2 的非负整数次幂;按面值从大到小取硬币,最小化凑出每个询问金额的硬币数。

来源 Codeforces 1003 D · 标签 贪心 / 二进制 / 位运算

题目描述

有 𝑛 枚硬币,第 𝑖 枚面值为 2{𝑘𝑖},其中 𝑘𝑖 是非负整数,面值不超过 109。

有 𝑞 次询问,每次给定 𝑥,求用硬币凑出 𝑥 所需的最少硬币数。每次询问独立,同一枚硬币在一次询问中至多使用一次。

1≤𝑛,𝑞≤2×105,1≤𝑥≤109。

题解

统计每个二进制位上有多少枚硬币。

对每个询问 𝑥,从高位到低位处理。设当前第 𝑖 位有 𝑐𝑖 枚面值为 2𝑖 的硬币,则最多取

min(𝑐𝑖,⌊𝑥2𝑖⌋)

枚。取完后从 𝑥 中减去对应的值,并累加硬币数。若处理完后 𝑥>0,说明无法凑出。

按高位优先取不会比用低位硬币更差:一枚 2𝑖 硬币最多可替代两枚 2𝑖−1 硬币,因此在能使用时优先使用大面值,硬币数不会增加。

复杂度

统计硬币为 𝑂(𝑛)。每个询问处理 𝑂(log109) 个二进制位,总时间为 𝑂(𝑛+𝑞log109),空间为 𝑂(log109)。

参考

源码位置