题目描述
银行排队
思路
- 首先将时间格式化成分钟,去除时间>17*60的,然后按照时间排序。
- 然后将窗口用堆存储,初始化每个窗口为480也就是8点。
- 然后每次取出最小的窗口值,如果当前要办理的客户时间大于窗口值,说明他不用等,直接办理,同时将他到达的时间+处理时间加入堆中,如果当前办理的用户时间小于窗口值,说明他要等,将等待时间记录下来,同时将窗口值+处理时间存入堆中。
C++ 代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 10010;
struct work{
double minutes;
int w;
bool operator < (const work& t) const{
return minutes < t.minutes;
}
};
int n,windows_n;
int main(){
cin>>n>>windows_n;
vector<double> window;
for(int i = 0; i < windows_n; i++) window.push_back(480);
make_heap(window.begin(),window.end(),greater<double>());
vector<work> list;
int num = n;
int hour,minute,second,w_t;
for(int i = 0; i < n; i++){
work k;
scanf("%d:%d:%d %d",&hour,&minute,&second,&w_t);
if(w_t > 60) w_t = 60;
double minutes = hour*60+minute+second/60.0;
if(minutes>17*60){
num--;
continue;
}
k.minutes = minutes;
k.w = w_t;
list.push_back(k);
}
sort(list.begin(),list.end());
double wait_after = 0;
for(int i = 0; i < list.size(); i++){
work p = list[i];
if(p.minutes<480){
p.minutes = 480;
}
}
for(int i = 0; i < num; i++){
work p = list[i];
pop_heap(window.begin(),window.end(),greater<double>());
double t = window.back();
window.pop_back();
if(p.minutes < t){
wait_after = wait_after + t - p.minutes;
window.push_back(t+p.w);
}
else{
window.push_back(p.minutes+p.w);
}
push_heap(window.begin(),window.end(),greater<double>());
}
printf("%.1lf", wait_after/num);
return 0;
}