CF1003D: Coins and Queries
硬币面值都是 2 的非负整数次幂;按面值从大到小取硬币,最小化凑出每个询问金额的硬币数。来源 Codeforces 1003 D · 标签 贪心 / 二进制 / 位运算
题目描述
有 枚硬币,第 枚面值为 ,其中 是非负整数,面值不超过 。
有 次询问,每次给定 ,求用硬币凑出 所需的最少硬币数。每次询问独立,同一枚硬币在一次询问中至多使用一次。
,。
题解
统计每个二进制位上有多少枚硬币。
对每个询问 ,从高位到低位处理。设当前第 位有 枚面值为 的硬币,则最多取
枚。取完后从 中减去对应的值,并累加硬币数。若处理完后 ,说明无法凑出。
按高位优先取不会比用低位硬币更差:一枚 硬币最多可替代两枚 硬币,因此在能使用时优先使用大面值,硬币数不会增加。
复杂度
统计硬币为 。每个询问处理 个二进制位,总时间为 ,空间为 。