1017 排队问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int K = 111;
const int INF = 1000000000;
struct Customer
{
int comeTime,serveTime;
}newCustomer;
vector<Customer> custom;
int convertTime(int h , int m , int s)//这个很好
{
return h * 3600 + m * 60 + s;
}
bool cmp(Customer a , Customer b)
{
return a.comeTime < b.comeTime;
}
int endTime[K]; //endTime[i]记录i号窗口的当前服务客户的结束时间
int main()
{
int c , w , totTime = 0;//totTime记录总的等待时长
int stTime = convertTime(8 , 0 , 0);
int edTime = convertTime(17 , 0 , 0);
scanf("%d%d" , &c , &w); //客户数,窗口数
int i;
for(i =0 ; i < w ; ++i)
{
endTime[i] = stTime;//没有客户,初始化为stTime
}
for(i = 0 ; i < c ; ++i)
{
int h , m , s, serveTime;
scanf("%d:%d:%d %d" , &h , &m , &s , &serveTime);
int comeTime = convertTime(h , m , s);
if(comeTime > edTime)
continue;
newCustomer.comeTime = comeTime;
newCustomer.serveTime = (serveTime <= 60? serveTime*60 : 3600);//服务时间多于1小时将强制压缩到一个小时
custom.push_back(newCustomer);
}
sort(custom.begin() , custom.end() , cmp);
for(i = 0 ; i < custom.size() ; ++i)
{
int idx = -1 , minEndTime = INF;
for(int j = 0; j < w ; ++j)
{
if(endTime[j] < minEndTime)
{
minEndTime = endTime[j];
idx = j;
}
}
//idx为最早结束窗口编号,将客户custom[i]分配到该窗口
if(endTime[idx] <= custom[i].comeTime)
{
//如果队首客户到达时间比该最早空闲窗口的时间要晚,那么客户可以直接前往服务,等待时间为0,令
//该窗口的endTime值增加该客户的服务时长
endTime[idx] = custom[i].comeTime + custom[i].serveTime;
}
else
{
//如果比其早,则客户需要等待俩者的时间差,然后才能前往服务,同样要更新endTime值
totTime += (endTime[idx] - custom[i].comeTime);
endTime[idx] += custom[i].serveTime;
}
}
if(custom.size() == 0)
printf("0.0");
else
printf("%.1f" , totTime / 60.0 / custom.size());
return 0;
}

热评文章