文章目录
这道题本身不难。但一直没有过,问题找了很久没没发现。看了别人的代码之后,才发现原来题目中讲的“Note that since the bank is closed everyday after 17:00, for those customers who cannot be served before 17:00, you must output "Sorry" instead.” 其实是说开始服务时间不能超过17:00而不是服务结束时间。
这题方法很多,无非都是排队。可以是用循环数组,也可以直接调用queue.方法一是自己写的,完完全全的模拟。方法二是看过其他人(http://blog.csdn.net/cloudbye/article/details/7792140)的思路后修正的,更简单,也不易错。
这题方法很多,无非都是排队。可以是用循环数组,也可以直接调用queue.方法一是自己写的,完完全全的模拟。方法二是看过其他人(http://blog.csdn.net/cloudbye/article/details/7792140)的思路后修正的,更简单,也不易错。
方法一:
#include <iostream> #include <queue> using namespace std; #define CUSTOMER_MAX 1000+1 #define INF 0x6fffffff #ifndef LOCAL // #define LOCAL #endif LOCAL int n; // number of windows <=20 int m ;// queue capacity <=10 int k; // customers <=1000 int q; // query times <=1000 int ProcessTime[CUSTOMER_MAX]; // queue<int> que[20]; queue<int >Wait[20]; int currTime = 0; int LeaveTime[CUSTOMER_MAX]; int Timebase[20] = {0}; int main() { #ifdef LOCAL freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif cin>>n>>m>>k>>q; for(int i=0;i<k;i++) { cin>>ProcessTime[i]; } int index; int top = 0; for(int i = 0;i<2*k;i++) { int min_len = m; if(top !=k) // if there are any customer not in line { for(int j=0;j<n;j++) { if(min_len > que[j].size() ) { min_len = que[j].size(); index = j; } } } if(min_len != m) // find minimum queue { que[index].push(top); Wait[index].push(ProcessTime[top]); top++; }else // no queue available or no customer not in line, then customer pop { long min_wait = INF; bool empty = true; for(int j=0;j<n;j++) { if(Wait[j].empty()) continue; if(min_wait > Timebase[j]+Wait[j].front()) // find current minimum wait time { min_wait = Timebase[j]+Wait[j].front(); index = j; empty = false; } } if(empty) break; Timebase[index] += Wait[index].front(); LeaveTime[que[index].front()] = Timebase[index]; que[index].pop(); Wait[index].pop(); } } //60*9 int qq; for(int i=0;i<q;i++) { cin>>qq; qq--; //if(LeaveTime[qq]<=60*9) // 题意看错了,悲了个剧的。是服务开始时间不超过17:00,而不是结束时间 if(LeaveTime[qq]-ProcessTime[qq]<60*9) { int hour = LeaveTime[qq]/60; int second = LeaveTime[qq]%60; printf("%02d:%02d\n",8+hour,second); } else printf("Sorry\n"); } #ifdef LOCAL system("PASUE"); #endif LOCAL return 0; }
方法二:
#include <iostream> #include <queue> #include <stdio.h> using namespace std; #define CUSTOMER_MAX 1000+5 #define INF 0x6fffffff int n; // number of windows <=20 int m ;// queue capacity <=10 int k; // customers <=1000 int q; // query times <=1000 int ProcessTime[CUSTOMER_MAX]; // queue<int> que[20+5]; int LeaveTime[CUSTOMER_MAX]={0}; int Timebase[20+5] = {0}; int main() { cin>>n>>m>>k>>q; for(int i=0;i<k;i++) { cin>>ProcessTime[i]; } int index; int top = 0; // n*m for (int i=0;top<m*n && top<k;top++) { que[i].push(top); LeaveTime[top] = Timebase[i]+ProcessTime[top]; Timebase[i] = LeaveTime[top]; i = (i+1)%n; } for(;top<k;top++) // pop and push { // find earliest leave customer int min_wait = INF; int found = false; for(int j=0;j<n;j++) { int cus = que[j].front(); if(min_wait > LeaveTime[cus]) // can not be empty { min_wait = LeaveTime[cus]; index = j; found = true; } } que[index].pop(); que[index].push(top); LeaveTime[top] = Timebase[index] + ProcessTime[top]; Timebase[index] = LeaveTime[top]; } while(q--) { int qq; cin>>qq; qq--; if(LeaveTime[qq]-ProcessTime[qq]>=60*9) { printf("Sorry\n"); } else { int hour = LeaveTime[qq]/60; int second = LeaveTime[qq]%60; printf("%02d:%02d\n",8+hour,second); } } return 0; }