题目链接: https://pintia.cn/problem-sets/1693095794755289088/exam/problems/type/7?problemSetProblemId=1693095890628689922&page=0
题意
一家面馆,有一批编号从1到m的订单,这批订单中有n种面,该面馆有编号从1到l的煮面篮子,每种面在篮子的需要煮的时间不同,师傅需要根据订单顺序开始下面,当有面下好时,捞取后,下一份订单的面才能下到该篮子里,如果同时有多份面完成,先放入编号较小的篮子,当有多份面完成,可以同时捞取但是根据订单编号的顺序配送。
最后要求第一行根据配送顺序依次输出各订单,格式为 订单编号:配送时间。第二行按照篮子编号顺序输出每个篮子下的订单数
思路
模拟的过程:先将前m个订单放入篮子中,找出这些篮子下的面中完成时刻最小的篮子,将该篮子里下下一份订单的面,每次都是如此。每次需要找到最小值,我们就可以想到小根堆。
小根堆里存放一个存有该面完成时刻和篮子编号的结构体,每次就能找到最先完成的篮子编号和时间,就可以存入答案里。
总体分为三个过程:
1.m个篮子还没有放满
2.m个篮子放满,订单还没放完,每次找出最先完成的篮子来放入后来的订单
3.订单放完,直接取堆顶
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
priority_queue<pair<int,int>>q;
int t[N];
int e[N];
int s[N];
struct A
{
int t,id;
}ans[N];
bool cmp(A a,A b)
{
if(a.t==b.t) return a.id<b.id;
return a.t<b.t;
}
int main()
{
int n,m,l;cin>>n>>m>>l;
int c=0;
for(int i=1;i<=n;i++) cin>>t[i];
for(int i=1;i<=l;i++){
int k;cin>>k;
if(i<=m){
q.push({-t[k],-i});
e[i]=i;
s[i]++;
}
else{
int time=-q.top().first;
int lz=-q.top().second;
q.pop();
ans[++c].t=time,ans[c].id=e[lz];
q.push({-(time+t[k]),-lz}); //默认是大根堆,弄成相反数和小根堆一个效果
e[lz]=i; //存储编号为lz的篮子上次煮的面的单号
s[lz]++;
}
}
while(q.size())
{
int time=-q.top().first;
int lz=-q.top().second;
q.pop();
ans[++c].t=time,ans[c].id=e[lz];
}
sort(ans+1,ans+1+l,cmp);
for(int i=1;i<=c;i++){
cout<<ans[i].id<<':'<<ans[i].t;
if(i!=c) cout<<' ';
}
cout<<"\n";
for(int i=1;i<=m;i++){
cout<<s[i];
if(i!=m) cout<<' ';
}
return 0;
}