2023 RoboCom CAIP本科组决赛-RC-u3 兰州拉面派餐系统

1.题目

题目链接：RC-u3 兰州拉面派餐系统 - 2023 睿抗机器人开发者大赛CAIP-编程技能赛-本科组（国赛） (pintia.cn)

2. 具体实现

模拟过程即可

2.1 普通方法

//模拟
#include<bits/stdc++.h>
using namespace std;
int times[10010];  //每种面需要的时间
int cus[100010];  //每个客户各自需要的时间 
int num[10010];  //记录每个篮子煮了多少次面 
int order[10010];  //记录每个篮子装的是哪位顾客的 
int shengy[10010];  //记录每个篮子面还需要多久 
map<int,int> p;  //存储出单次序+最小坐标 
vector<int> p1; //按照菜篮顺序 
int n,m,l;
int temp;
int getMin(){p.clear(); p1.clear(); int mi=0x3f3f3f3f;for(int i=1;i<=m;i++){if(shengy[i]!=0&&shengy[i]<mi)mi=shengy[i];}//找到最小值的坐标for(int i=1;i<=m;i++){if(mi==shengy[i]){p1.push_back(i);int o=order[i];  //记录是哪一位顾客的 p[o]=i; }}return mi; 
} 
//判断是否都煮好了 
bool judge(){for(int i=1;i<=m;i++){if(shengy[i]!=0)return false;}return true; 
}
int main(void){cin>>n>>m>>l;  //面的种类数、篮子个数for(int i=1;i<=n;i++){cin>>times[i];}for(int i=1;i<=l;i++){int t;cin>>t;cus[i]=times[t];}//初始化for(int i=1;i<=min(m,l);i++){order[i]=i;num[i]=1;shengy[i]=cus[i]; }int tim=min(m,l);  //表示已经煮了第几客单 //模拟int t=0;  //经过的时间 bool flag=true;  //false表示不是第一个 while(1){int minz=getMin();//p存储位置，找到位置，将值归为0，客单拿出来t+=minz;//所有剩余都要减去for(int i=1;i<=m;i++){if(shengy[i]!=0)shengy[i]-=minz;}//捞出 for(auto x:p){int o=x.first;  //次序（第几个客人） if(!flag) cout<<" ";flag=false; 
//			int z=x.second;  //坐标 cout<<o<<":"<<t;}//加面for(int i=0;i<p1.size();i++){if(tim<l){tim++;shengy[p1[i]]=cus[tim];order[p1[i]]=tim;num[p1[i]]++;}}if(judge()){break;} }cout<<endl;for(int i=1;i<=m;i++){if(i!=1) cout<<" ";cout<<num[i]; } return 0;
} 

2.2 使用优先队列

//捞面：每个篮子按时间短的先，如果时间相同，按篮子序号从小到大 
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
const int M=10010;
//第一个捞出的位置 
//时间最早，如果时间相同，捞出lanzi最小的面 
struct node{int lanzi;  //第几个篮子 int tt;     //需要的时间 int order;  //派单序号 bool operator<(const node& a) const{return tt==a.tt?lanzi>a.lanzi:tt>a.tt; } 
};
priority_queue<node> p;
int times[N];  //每种面所需要的时间
queue<pair<int,int> > q;  //客单顺序、面的种类 
vector<pair<int,int>> res; //编号、时间 
int num[M];  //记录篮子的使用次数 
int main(void){int n,m,l;cin>>n>>m>>l;for(int i=1;i<=n;i++){cin>>times[i];}for(int i=1;i<=l;i++){int t;cin>>t;q.push({i,t});}//模拟场景int cnt=1;  //用于分配的篮子编号 while(!q.empty()){auto z=q.front();q.pop();if(cnt<=m){  //表明还有空闲篮子 p.push({cnt,times[z.second],z.first}); num[cnt++]++; }else{//t就是我们捞出的地方 node t=p.top();p.pop();res.push_back({t.tt,t.order}); p.push({t.lanzi,t.tt+times[z.second],z.first});num[t.lanzi]++; } }while(p.size()){auto z=p.top();p.pop();res.push_back({z.tt,z.order});}sort(res.begin(),res.end());//输出结果for(int i=0;i<res.size();i++){if(i!=0) cout<<" ";cout<<res[i].second<<":"<<res[i].first;}cout<<endl;for(int i=1;i<=m;i++){if(i!=1) cout<<" ";cout<<num[i];} 	return 0;
}