CJBS03｜累计进度查询 题解

核心算法

先计算前缀和，再二分第一个不小于目标 $x$ 的前缀和。

思路推导

因为每天完成数量非负，前缀和序列单调不下降，即使某天完成 $0$ 个任务也不会破坏单调性。于是“累计值是否至少为 $x$”具有明显的真假分界。

正确性说明

第 $d$ 天前缀和正是前 $d$ 天累计完成量。二分得到第一个满足 prefix[d] >= x 的位置，因此此前每一天均未达标，而第 $d$ 天已经达标，恰好是最早答案。若不存在满足位置，则最终累计量也不足，输出 -1。

复杂度

• 建立前缀和：$O(n)$；
• 每次查询：$O(\log n)$；
• 总时间：$O(n+q\log n)$；
• 空间：$O(n)$。

易错点

• 前缀和与目标均使用 long long；
• 某天增量可以为 0，前缀和可能重复；
• 要找“达到或超过”，条件是 >=；
• 目标超过总和时输出 -1。