B4204题解

洛谷同文链接

题意

给你 $n$ 根青菜，$m$ 个机器人，机器人洗菜用 $a$ 的时间，做菜用 $b$ 的时间。求多久之后菜能做好。

思路

使用一个小根堆调度。确保每次出队的都是最早空闲的机器人。

然后先让机器人完成所有物品的清洗，对于每个机器人，完成清洗任务后再次进入队列，作为空闲机器人等待下一次使用。

当所有的菜都洗碗之后，让空闲的机器人从处理洗菜任务变成开始处理水煮任务。水煮任务的处理逻辑同以上的逻辑。

最后，追踪每一个物品的水煮完成时间，最终计算出的最大时间即为所有物品水煮完成时间的最大值。

代码

AC记录

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	int n,m,a,b;
	cin>>n>>m>>a>>b;

	priority_queue<int,vector<int>,greater<>> robot;// 空闲机器人的时间
	for(int i=0;i<m;i++) robot.push(0);//初始化

	vector<int>wash_end;// 清洗完成时间
	int wash_cnt=0,boil_cnt=0;// 已完成的清洗次数和水煮次数

	priority_queue<int,vector<int>,greater<>> wash_finish;// 水煮完成时间

	while(!robot.empty()){
		int t=robot.top();robot.pop();
		if(wash_cnt<n){//处于开机状态（清洗次数未到）
			wash_end.push_back(t+a);
			robot.push(t+a);
			wash_cnt++;
		}
		else if(boil_cnt<n){// 清洗次数已到（关机）
			int start_time=max(t,wash_end[boil_cnt]);// 取清洗完成时间和当前时间的较大值，即为最后的开机的时间
			wash_finish.push(start_time+b);
			robot.push(start_time+b);
			boil_cnt++;
		}
	}

	int ans=0;
	while(!wash_finish.empty()){//统计总时间
		ans=max(ans,wash_finish.top());
		wash_finish.pop();
	}

	cout<<ans;
	return 0;
}