自动搬运

查看原文

来自洛谷，原作者为

	Sliarae Re:start

搬运于2025-08-24 21:17:50，当前版本为作者最后更新于2025-03-08 13:01:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

容易想到维护一个小根堆 $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; 
}