P10605

chen_zhe · 2024-06-16 21:08:35 · 题解

容易发现为了完成任务的时间最短，对于当前长度为 x 的任务，每次莲子会选择一个最早的时间 t 满足 t 到 t+x-1 均是空闲的。

接下来观察到：选择的时间 t 一定要么是上次结束任务的时间，要么是某个非空闲日子 b_i 的下一天 b_i+1。遍历数组 b 并记录上次结束任务的时间和当前进行到第几项任务，可以做到 O(n+m) 的复杂度。