思路

设 $T_i,C_i$ 分别为处理时间与费用系数的前缀和，$f_i$ 表示前 $i$ 个任务已经分批后的最小贡献。若最后一批是 $j+1$ 到 $i$，则

整理后，需要在所有 $j<i$ 中最小化

做法

把每个 $j$ 看作斜率为 $-C_j$、截距为 $f_j$ 的直线，在横坐标 $T_i+S$ 处查询最小值。由于 $T_i$ 严格递增，$C_i$ 单调不降，直线斜率和查询横坐标都有序，可以用单调队列维护下凸壳。相同斜率只保留截距更小的直线。

正确性证明

启动第一个批次会让所有任务推迟 $S$，以后每增加一个批次，会让该批及其后所有任务再推迟 $S$。因此以 $j+1$ 开始最后一批时，启动时间贡献为 $S(C_N-C_j)$，处理完成时刻贡献为 $T_i(C_i-C_j)$，递推式完整且不重不漏。

凸壳中保存了所有可能作为最后一批前缀的转移直线。单调队列删除的直线在当前及以后更大的查询横坐标上都不可能优于相邻直线，因此不会删除任何最优转移。每次查询得到递推式的最小值，所以按 $i$ 归纳，所有 $f_i$ 均正确，最终 $f_N$ 即答案。

复杂度分析

每条直线至多入队、出队一次，时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。