1685-银行排队

题目描述

我们大多都有在银行排队的经历，唉，那坑爹的排队啊！现在就让我们来算算我们这些客户平均需要等多久吧。
每天刚开始时银行会开m个窗口来为我们total个客户办理业务，当有客户需要办理业务时，先选择可以办理业务的窗口，如果有多个窗口可以办理业务就选择空闲时间最长的窗口，如果有多个窗口空闲的时间一样长，则选择序号小的窗口办理业务。假设我们每个人来到的时间和办理业务所需要的时间（为了简化问题，采用整数表示时间）都知道了。现在请你算算我们平均需要等待多久呢？

输入

有多组测试数据，每组数据开始有两个正整数m(<20)和total(<200)，后面有total对整数，对应客户先后到来的时间以及办理业务所需的时间。

输出

平均等待的时间，保留两位小数。

样例输入

2 6 1 3 4 1 5 3 9 2 13 4 13 3
3 14 0 3 2 2 2 4 5 4 7 2 11 3 12 3 12 4 12 1 13 3 15 4 19 1 22 3 23 2
2 5 0 6 0 5 0 6 7 1 7 2

样例输出

0.00
0.29
1.20

在这个排队问题中，题目是空闲时间最多的窗口最先被排队，换个说法便是该窗口的队列时间最短，另外当窗口队列时间一样时，选择窗口序列最小的进行排队。
正是由于只要判断队列时间长短，于是我们可以采取每个来客都进行窗口时间比较，选择队列时间少的或是窗口序列小的那个窗口。这是就要考虑人需要等待的时间和队列时间长度的更新。
如队列时间小于或等于某个客户到来时间，很明显该窗口的队列时间就等于客户到来时间加上办理时间，后面来的人只能在该客户办完后才能办理业务。
如队列时间大于某个客户到来时间，那该客户就需要等待前面的客户办理完后，才能办理，此时等待时间就等于该窗口队列时间减去该客户到来时间点，该窗口的新的队列时间就等于前队列时间加上该客户的办理时间。
所以该程序代码如下所示：

 1 #include "stdio.h"
 2 #include "math.h"
 3 #include "stdlib.h"
 4 #include "string.h"
 5 
 6 int select(int *p,int m)
 7 {
 8     int temp;
 9     int number;
10     int i=1;
11     temp = *p;
12     number = 0;
13     for(i=1; i<m; i++)
14     {
15         if(*(p+i)<temp)
16         {
17             temp = *(p+i);
18             number = i;
19         }
20     }
21     return number;
22 }
23 void output(int *a )
24 {
25     int i,j;
26     int temp;
27     int time = 0;
28     int m,total;
29     int last[20];
30     m=*a;
31     total = *(a+1);
32     for(i=0; i<m; i++)
33     {
34         last[i]=0;
35     }
36     for(i=1; i<(total+1); i++)
37     {
38         temp = select(last,m);
39         if(last[temp]>a[2*i])
40         {
41            time = time + last[temp] - a[2*i];//队长时间减去到来时间等于等待时间
42            last[temp] = last[temp] + a[2*i+1];//队长时间加办理时间等于新队长时间
43         }
44         else if(last[temp]<=a[2*i])
45         {
46             last[temp] = a[2*i] + a[2*i+1];//到来时间加办理时间等于新队长时间
47         }
48     }
49 
50     printf("%.2f\n",(float)time/(float)total);
51 }
52 int main()
53 {
54     int i;
55     int j=0;
56     int a[404];
57     int c;
58      while(scanf("%d",&a[0])!=eof)
59      {
60          scanf("%d",&a[1]);
61          for(i=1; i<=a[1]; i++)
62          {
63              scanf("%d%d",&a[2*i],&a[2*i+1]);
64          }
65          output(a);
66      }
67     return 0;
68 }