CF452D Washer, Dryer, Folder 题解

· · 题解

思路

由于每个洗衣机的用时都是一样的，不妨规定按照【第 0 个洗衣机 \rightarrow 第 1 个洗衣机 \rightarrow 第 2 个洗衣机 \rightarrow\cdots \rightarrow 第 n_1-1 个洗衣机 \rightarrow 第 0 个洗衣机 \rightarrow 第 1 个洗衣机\rightarrow\cdots】的顺序使用。其它机器同理。

用 f_1[x] 表示第 x 个洗衣机洗完一件衣服的结束时间。其它机器同理，用 f_2 和 f_3 表示。

对于第 i 件衣服，按照上面的规则，用第 i\bmod n_1 个洗衣机，第 i\bmod n_2 个烘干机，第 i\bmod n_3 个熨斗。

考虑到中途不能停留，所以结束时间 \textit{finish} 为

\max(f_1[i\bmod n_1]+t_1+t_2+t_3, f_2[i\bmod n_2]+t_2+t_3, f_3[i\bmod n_3]+t_3)

然后更新

\begin{aligned} &f_1[i\bmod n_1] = \textit{finish} - t_2 - t_3\\ &f_2[i\bmod n_2] = \textit{finish} - t_3\\ &f_3[i\bmod n_3] = \textit{finish} \end{aligned}

答案为洗完最后一件衣服的结束时间。

复杂度分析

AC 代码（Golang）

package main
import . "fmt"
func max(a, b int) int { if b > a { return b }; return a }

func main() {
    var k, n1, n2, n3, t1, t2, t3, finish int
    Scan(&k, &n1, &n2, &n3, &t1, &t2, &t3)
    f1 := make([]int, n1)
    f2 := make([]int, n2)
    f3 := make([]int, n3)
    for i := 0; i < k; i++ {
        finish = max(max(f1[i%n1]+t1+t2+t3, f2[i%n2]+t2+t3), f3[i%n3]+t3)
        f1[i%n1] = finish - t2 - t3
        f2[i%n2] = finish - t3
        f3[i%n3] = finish
    }
    Print(finish)
}