饮料：题解

思路

前 $t_i$ 分钟最多制作 $t_i$ 杯，所以可行的必要条件是每个前缀都满足 $t_i\ge i$；下面的逆序构造也证明它充分。

从晚到早处理到达时刻。栈表示已经引入但尚未分配生产分钟的强制杯量，且从栈底到栈顶单调不减。逆序引入顾客 $i$ 时压入 max(a[i], top)：更晚顾客可能取走大杯，因此当前顾客所对应的杯不能低于尚未结算的最大强制量。

做法

同一时刻的顾客必须按编号从大到小全部压栈，再使用该时刻及此前空档的生产槽。若当前不同到达时刻为 $\tau$、前一时刻为 $p$，共有 $\tau-p$ 个槽；每个槽弹出栈顶并把其体积加入答案，直到槽或栈用尽。

优先结算当前最大强制杯是最优的：若更大的未决杯被安排得更早，而较小杯更晚，交换不会破坏截止时刻，并可减少大杯向中间顾客传播的影响。

子任务 1 的到达严格递增，每人可在自己的到达分钟制作体积恰为 $a_i$ 的杯，答案是需求和。子任务 2 可逐分钟逆序扫描；满分直接批量处理空档。

复杂度

每名顾客恰好进出栈一次，时间复杂度 $O(n)$，空间复杂度 $O(n)$。