题解

算法思路

这个代码实现了一个高效的解决方案，用于找到在贪心纸币分配算法下，不超过给定金额 $b$ 时所需纸币数量的最大值。

核心思想

1. 预处理阶段：

   • 定义 $f[i]$ 表示使用前 $i$ 种面额时，贪心算法能达到的最大金额
   • 定义 $id[i]$ 表示达到 $f[i]$ 时使用的纸币数量
   • 对于每个面额 $a_i$，计算能重复使用 $a_{i-1}$ 的最大次数，使得总金额不超过 $a_i - 1$

2. 状态转移：

   • $tmp = \lfloor (a_{i+1} - f[i] - 1) / a_i \rfloor$
   • $f[i+1] = f[i] + tmp \times a_i$
   • $id[i+1] = id[i] + tmp$

3. 查询处理：

   • 对于每个查询 $b$，找到最大的 $pos$ 满足 $a_{pos} \leq b$
   • 计算还能额外添加多少张 $a_{pos}$ 面额的纸币
   • 输出总金额和纸币数量

算法正确性分析

该算法基于贪心算法的性质：

• 在面额系统中，最坏情况通常出现在金额刚好小于某个大面额时
• 通过预处理，我们记录了在每个面额切换点时的最优状态
• 查询时只需在预处理的基础上进行简单计算

复杂度分析

• 预处理：$O(n)$
• 每个查询：$O(\log n)$（二分查找）
• 总复杂度：$O(n + q\log n)$，能够处理 $n, q \leq 2\times 10^5$ 的数据规模

示例验证

对于样例输入：

4
1 5 10 50
3
2
8
50

预处理得到的 $f$ 和 $id$ 数组能够正确计算出：

• $b=2$ → $2\ 2$
• $b=8$ → $8\ 4$
• $b=50$ → $49\ 9$

算法标签

• 动态规划
• 贪心算法
• 二分查找
• 预处理优化
• 数学计算

核心结论

该解法通过巧妙的预处理，将原本需要模拟贪心过程的问题转化为简单的数学计算，充分利用了贪心算法的单调性和面额系统的特性，实现了高效的问题求解。