题解：B4204 [常州市程序设计小能手 2021] 烧菜

· · 题解

容易想到维护一个小根堆 q，q 中的一个数 x 表示在 x 时刻一个机器人做完了手中的事情，处于空闲状态。

那么我们一开始在 q 中加入 m 个 0。每次取 q 的堆顶 t。此时我们认为已经到达了时间 t，于是就获得一个空闲的机器人。

我们给它分配任务：维护未清洗的白菜数量 p 和未水煮的白菜数量 q。若 p > 0，则让这个机器人在 [t, t + a) 这个时间段内清洗白菜，相当于在 q 中加入 t + a，并令 p \gets p - 1。否则类似的在队列中加入 t + b，并令 q \gets q - 1。

但是这样做有问题。可能出现一个机器人想煮菜，但还没有菜被洗完的情况。hack 数据如下：

3 2 1000 1

这时上述算法会输出 2000，但答案为 2001。

考虑额外维护小根堆 p，表示下一个洗完的白菜什么时候才能到。一个时间为 t 的机器人洗菜的时候同时在 p, q 中加入 t + a。而煮菜的时候判一下 t 是否小于 p 的堆顶，如果小于就将 p 的堆顶放入 q，并什么也不做。

#include <iostream>
#include <queue>

using namespace std;

int n, m, t, a, b;

int main () {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> a >> b, t = n, m = min(m, n);
    priority_queue<int, vector<int>, greater<int>> q, p;
    for (int i = 1; i <= m; ++i) q.push(0);
    while (n || t) {
        int tp = q.top();
        q.pop();
        if (n) --n, p.push(tp + a), q.push(tp + a);
        else if (tp + b < p.top()) q.push(p.top()); 
        else --t, p.pop(), q.push(tp + b);
    }  
    int ans = 0; 
    for (; !q.empty(); q.pop()) ans = q.top();
    cout << ans << '\n';
    return 0; 
}