解题思路
任务必须按编号切成连续若干天,每天是数组上的一段。每天最多把 q 卷交给支援技师,双方耗时都不能超过 480,目标是最小化主技师单日耗时的最大值 T。天数不能超过 d,可以更少。
- 先判定 T=480 是否可行。主技师每天也只有 480 分钟,若这一档都排不完,答案就是 −1。
- 在 [0,480] 上二分 T。判定时从左到右贪心:能把当天往后多接一卷就多接,接不动再新开一天。段可做具有单调性,贪心用的天数最少。
- 判断「当前这一天再加一卷是否合法」:用位集记录支援技师的耗时。dp[t] 的第 s 位表示已经交接 t 卷、支援耗时恰好为 s。
- 新来一卷若不超过 T,可以选择留给主技师或交给支援;若超过 T,只能交给支援。支援耗时大于 480 的状态直接丢掉。
- 当天总和为 S 时,需要存在一种交接使得支援耗时至少 S−T(从而主技师不超过 T)。q≤10,位集长度只有 481,转移足够快。