1014 Waiting in Line (30分)解题思路

本文主要是介绍1014 Waiting in Line (30分)解题思路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1014 Waiting in Line (30分)解题思路

原题链接

这题我觉得有点难度，细节上的东西不少，最重要的思想是要设定一个统一的时间轴timeLine。

思路

设置N个队列（每个窗口都对应一个队列），队列长度最大为M，初始化的时候将每个人的编号填入所有的队列，如果填满了N*M，就停止填充，剩下的编号作为排队线以外的顾客编号。填充方法如下图
在这里插入图片描述
另外，开辟一个数组cost_time[]，cost_time[i]表示顾客i办理业务的耗时

然后开启循环，在所有队列的首部中找出耗时最少的顾客的编号，假设下图中的黑色圆圈中的编号2顾客的cost_time[2]是编号1,2,3,4中耗时最少的，则把1,2,3,4的耗时都减去cost_time[2]，即
cost_time[i] = cost_time[i] - cost_time[2] (i=1, 2, 3, 4)
在这里插入图片描述

与此同时，时间轴往后推进,timeLine = timeLime + cost_time[2]

如果减完后cost_time[i] = 0，则说明顾客i已经办完业务了，记录下i的结束时间为此时的time_line。

然后更新队列，将队列首部中cost_time为0的顾客编号pop掉，将排队线以外的新顾客添加到队尾。

重复上述操作直至队列为空。

AC代码

#include <iostream>
#include <queue>
using namespace std;queue<int>queue_[21];
int cost_time[1002];        //每个人办理业务的耗时
int cost_time_backup[1002]; //cost_time的备份数组。后面要用
int inquiryID[1002];//询问者的ID
int N, M, K, Q;     //N: 总窗口数     M:  队列长度    K:  客户数      Q:  询问数
int count_;         //队列中填充过的人数
int timeLine;       //时间线，这是统一的时间轴
int leave_time_table[1002];//完成办理的时刻
//找出所有队列的队列首元素中
int findSmallestCost(){int min = 999999;int index=-1;for(int i=1; i<=N; i++){if(queue_[i].size() == 0){continue;}else if(cost_time[queue_[i].front()] < min){min = cost_time[queue_[i].front()];index = queue_[i].front();}}return index;//如果返回-1说明所有的队列已经空了
}
//更新队列
void update(){for(int i=1; i<=N; i++){if(queue_[i].size()>0 && cost_time[queue_[i].front()] == 0){queue_[i].pop();if(count_ <= K)//如果填充的数量还小于K，则在此队列中填充一个人queue_[i].push(count_++);}}
}    
void showTime(){int ID;int hour, minute;int time;for(int i=1; i<=Q; i++){ID = inquiryID[i];time = leave_time_table[ID];hour = time / 60 + 8;minute = time % 60;if(time - cost_time_backup[ID] >= 540)printf("Sorry\n");elseprintf("%02d:%02d\n", hour, minute);}
}
int main(){count_ = 1;cin>>N>>M>>K>>Q;for (int i=1; i<=K; i++){cin>>cost_time[i];cost_time_backup[i] = cost_time[i];}for(int i=1; i<=Q; i++){cin>>inquiryID[i];}int flag = 0;int i=1,j=1;//首次填充队列for(i=1; i<=M; i++){for(j=1; j<=N; j++){if(count_ > K){//如果填充的数量等于了K，则停止填充flag = 1;break;}queue_[j].push(count_);count_++;}if(flag == 1)break;}int index;int dec;for(;;){index = findSmallestCost();if(index == -1)break;dec = cost_time[index];timeLine += dec;//cout << timeLine << endl;for(int i=1; i<=N; i++){if(queue_[i].size() > 0){cost_time[queue_[i].front()] -= dec;if(cost_time[queue_[i].front()] == 0){leave_time_table[queue_[i].front()] = timeLine;}}}update();}showTime();return 0;
}