题解：B4204 [常州市赛 2021] 烧菜

· · 题解

或许更好的阅读体验

题意

给你 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;
}