观察:一组工作能被 $a$ 个工人完成当且仅当任意时刻同时进行的工作数量不超过 $a$。
我们先把工作分配给清醒工人,满足以下两个条件:
- 所有困难工作都被完成。
- 每个时刻未完成的简单工作数量不超过 $b$。
我们用一条长度 $2m$ 的链表示时间,流过链上的边 $i\to i+1$ 表示一个工人在 $[i,i+1)$ 这段时间是空闲的。每个工作 $[l,r)$ 连边 $l\to r$,容量为 $1$;并且如果是困难工作,则这条边的下界也为 $1$。源点连向链首和链尾连向汇点的边容量为 $a$。
对于第二个限制,如果 $[i,i+1)$ 时间段有 $c_i$ 个工作需要完成,则其中至少有 $c_i-b$ 个需要被清醒工人完成,也就是说在 $[i,i+1)$ 这段时间空闲的工人数量不能超过 $a-(c_i-b)$,因此 $i\to i+1$ 的容量就是 $a-(c_i-b)$。
建图后跑一个上下界可行流,流量、点数、边数都是 $O(m)$,因此复杂度不超过 $O(m^2)$。