题目描述

我们大多都有在银行排队的经历，唉，那坑爹的排队啊！现在就让我们来算算我们这些客户平均需要等多久吧。
每天刚开始时银行会开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

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

#include "stdio.h"
#include "math.h"
#include "stdlib.h"
#include "string.h"

int select(int *p,int m)
{
    int temp;
    int number;
    int i=1;
    temp = *p;
    number = 0;
    for(i=1; i<m; i++)
    {
        if(*(p+i)<temp)
        {
            temp = *(p+i);
            number = i;
        }
    }
    return number;
}
void output(int *a )
{
    int i,j;
    int temp;
    int time = 0;
    int m,total;
    int last[20];
    m=*a;
    total = *(a+1);
    for(i=0; i<m; i++)
    {
        last[i]=0;
    }
    for(i=1; i<(total+1); i++)
    {
        temp = select(last,m);
        if(last[temp]>a[2*i])
        {
           time = time + last[temp] - a[2*i];//队长时间减去到来时间等于等待时间
           last[temp] = last[temp] + a[2*i+1];//队长时间加办理时间等于新队长时间
        }
        else if(last[temp]<=a[2*i])
        {
            last[temp] = a[2*i] + a[2*i+1];//到来时间加办理时间等于新队长时间
        }
    }

    printf("%.2f\n",(float)time/(float)total);
}
int main()
{
    int i;
    int j=0;
    int a[404];
    int c;
     while(scanf("%d",&a[0])!=EOF)
     {
         scanf("%d",&a[1]);
         for(i=1; i<=a[1]; i++)
         {
             scanf("%d%d",&a[2*i],&a[2*i+1]);
         }
         output(a);
     }
    return 0;
}