题解

问题分析

题目要求计算将 $l$ 件衣服全部洗干净并烘干的最少时间。关键约束是：每台洗衣机和烘干机每次只能处理一件衣服，且衣服必须先洗后烘（可间隔一段时间）。核心目标是合理调度洗衣机和烘干机，最小化全部衣服完成洗涤和烘干的总时间。

核心思路

1. 洗衣机调度：为了使洗涤阶段的完成时间尽可能早，应优先使用当前最早可用的洗衣机。通过最小堆（优先队列）维护洗衣机的下次可用时间，每次选择最早空闲的洗衣机处理下一件衣服，记录每件衣服的洗涤完成时间。

2. 烘干机调度：同理，烘干阶段需基于洗涤完成时间，优先使用当前最早可用的烘干机。同样用最小堆维护烘干机的下次可用时间，对于每件衣服，其烘干开始时间为洗涤完成时间与烘干机下次可用时间的最大值，记录每件衣服的烘干完成时间（总时间）。

3. 结果计算：所有衣服的烘干完成时间中的最大值，即为全部衣服处理完毕的最少时间。

算法步骤

1. 洗衣机处理：

   • 将所有洗衣机的初始可用时间（即单次洗涤时间 $w_i$）加入最小堆。
   • 重复 $l$ 次：取出堆中最早可用的洗衣机（堆顶元素），记录当前衣服的洗涤完成时间（即该洗衣机的当前可用时间），更新该洗衣机的下次可用时间（当前时间 + 自身洗涤时间）并放回堆中。
   • 得到数组 tot，其中 tot[i] 表示第 $i$ 件衣服的洗涤完成时间。

2. 烘干机处理：

   • 将所有烘干机的初始可用时间（即单次烘干时间 $d_i$）加入最小堆。
   • 按洗涤完成时间的顺序（tot 数组的顺序，因洗涤调度后 tot 是递增的），对每件衣服进行烘干调度：取出堆中最早可用的烘干机，计算该衣服的烘干完成时间（max(tot[i], 烘干机当前可用时间) + 烘干机时间），更新烘干机的下次可用时间并放回堆中，同时更新 tot[i] 为烘干完成时间。

3. 求结果：tot 数组中的最大值即为最少总时间。

代码解析

• 优先队列（最小堆）：通过自定义结构体 node 的 < 运算符（逆序定义，使堆顶为最小元素），实现最小堆功能，高效获取最早可用的机器。
• 洗衣机调度循环：循环 $l$ 次，每次从堆中取出最早可用的洗衣机，记录洗涤完成时间，更新后放回堆，得到 tot 数组。
• 烘干机调度循环：同样循环 $l$ 次，基于 tot 数组的洗涤完成时间，调度烘干机，更新 tot 为烘干完成时间。
• 结果计算：遍历 tot 数组取最大值，即为答案。

复杂度分析

• 时间复杂度：$O(l \log n + l \log m)$。洗衣机和烘干机的调度各需 $l$ 次堆操作，每次堆操作（插入/弹出）的时间复杂度为 $O(\log n)$ 或 $O(\log m)$（$n$ 和 $m$ 分别为洗衣机和烘干机数量）。
• 空间复杂度：$O(n + m + l)$。用于存储洗衣机/烘干机时间、堆（最多 $n$ 或 $m$ 个元素）及 tot 数组（$l$ 个元素）。

综上，算法通过贪心策略结合优先队列，高效调度机器，确保总时间最小，适用于大规模输入数据（$l \leq 10^6$）。