#include <stdio.h>
#define SIZE 20
typedef struct{
int ArrivalTime; // 客户到达银行的时间
int Duration; // 客户办理业务的所需要的时间
}CustomerType; // 客户的数据结构
int windows[SIZE]; // 记录 银行窗口当前何时可以接受下一位客户
int total_time; // 记录用户总共等待的时间
CustomerType customers[200];// 客户到达银行的队列,使用数组来表述队列
int total; // 记录当前客户的总数,其实就是队列的队尾
void BankOpen(){
// 银行开门
int i;
for(i=0; i<SIZE; i++){
windows[i] = 0; // 刚开始窗口一开始都可以接纳客户
}
total_time = 0; // 总等待的时间与客户人数为 0
}
void CustomerIn(int total){
int i = 0;
while(i < total){ // 我们将一天中所有的顾客到来的时间和办理业务所需时间读进来
scanf("%d%d",&customers[i].ArrivalTime, &customers[i].Duration);
i++;
}
}
void Deal(int m, int n){
// m 个窗口办理客户的业务
int i, j;
int minTimeIndex; // 某个时刻,m 个窗口中最快办理完业务的窗口编号
for(i=0; i<n; i++){ // 依次办理 n 个客户的业务
minTimeIndex = 0;
for(j=1 ;j<m ;j++){ // 在 m 个窗口中查找最快办理完业务的编号
if(windows[minTimeIndex] > windows[j]){
minTimeIndex = j;
}
}
if(windows[minTimeIndex] <= customers[i].ArrivalTime){
// 如果客户不需等待
// 则该窗口可以接待下一位客户的时间为当前客户到达的时间加上办理的时间
windows[minTimeIndex] = customers[i].ArrivalTime + customers[i].Duration;
}else{
// 如果客户需要等待,则总等待时间就会增加
// 同时该窗口可以接待下一位客户的时间为当前接待时间加上办理所需时间
total_time += windows[minTimeIndex] - customers[i].ArrivalTime;
windows[minTimeIndex] += customers[i].Duration;
}
}
}
int main(){
int m; // 存储窗口数目
while(scanf("%d%d",&m ,&total) != EOF){
BankOpen(); // 银行开门
CustomerIn(total); // 迎接客户
Deal(m, total); // m 个窗口办理 total 个客户的业务
printf("%.2lf\n", total_time*1.0/total); // 计算平均等待时间
}
return 0;
}
/**************************************************************
Problem: 2147
User: admin
Language: C++
Result: Accepted
Time:11 ms
Memory:1148 kb
****************************************************************/