CJBS07｜多机生产计划 题解

核心算法

二分最早达标时间，使用计数公式完成 check，并对总产量做截断防溢出。

思路推导

给定时刻 $T$：若 $T<s_i$，第 $i$ 台机器产量为 $0$；否则产量为

随着时间增加，总产量只增不减，因此“总产量是否至少为 $m$”具有单调性。寻找第一个为真的时间即可。

正确性说明

公式准确计算每台机器在时刻 $T$ 已完成的产品数，总和至少为 $m$ 当且仅当 $T$ 已经达标。达标状态随时间保持为真，故所有时刻形成“未达标—已达标”的分界。二分结束时 left 是第一个达标时刻，即最早答案。

复杂度

• 每次检查：$O(n)$；
• 二分最多约 $60$ 次；
• 总时间：$O(n\log10^{18})$；
• 额外空间：$O(1)$。

易错点

• $T<s_i$ 时产量必须是 0；
• 第一件产品在 $s_i$ 秒完成，因此达标后的公式要加 1；
• 多台机器产量直接累加可能超过 long long，达到 $m$ 后应立即返回，或在加法前做截断；
• 本题找最小可行时间，更新方向与“最大可行值”相反；
• 上界与中点均使用 long long。