算法核心思路

关键观察

• 第 $k$ 天来的 $a_k$ 个客人，每人买的包装编号是：$a_k, 2a_k, 3a_k, \dots$
• 但如果某个包装已被前面的客人买走，就要跳过它找下一个可用的

高效解法

使用 位置指针数组 $\text{pos}[x]$ 来记录对于倍数 $x$，下一个可用的最小包装编号。

算法步骤：

1. 初始化 $\text{pos}[x] = x$（每个倍数从自身开始）
2. 对于第 $k$ 天的 $a_k$ 个客人：
   • 对于第 $j$ 个客人：
     • 从 $\text{pos}[a_k]$ 开始找可用包装
     • 如果 $\text{pos}[a_k]$ 已被购买，则 $\text{pos}[a_k] \gets \text{pos}[a_k] + a_k$
     • 购买 $\text{pos}[a_k]$，如果它有礼券则记录客人编号
     • 更新 $\text{pos}[a_k] \gets \text{pos}[a_k] + a_k$

时间复杂度

• 每个包装最多被访问一次
• 总复杂度：$O(N + M)$，其中 $N$ 是最大包装编号，$M$ 是总客人数