Suppose a bank has  windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. All the customers have to wait in line behind the yellow line, until it is his/her turn to be served and there is a window available. It is assumed that no window can be occupied by a single customer for more than 1 hour.

Now given the arriving time  and the processing time  of each customer, you are supposed to tell the average waiting time of all the customers.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 numbers:  () – the total number of customers, and  () – the number of windows. Then  lines follow, each contains 2 times: HH:MM:SS – the arriving time, and  – the processing time in minutes of a customer. Here HH is in the range [00, 23], MM and SS are both in [00, 59]. It is assumed that no two customers arrives at the same time.

Notice that the bank opens from 08:00 to 17:00. Anyone arrives early will have to wait in line till 08:00, and anyone comes too late (at or after 17:00:01) will not be served nor counted into the average.

Output Specification:

For each test case, print in one line the average waiting time of all the customers, in minutes and accurate up to 1 decimal place.

Sample Input:

7 3
07:55:00 16
17:00:01 2
07:59:59 15
08:01:00 60
08:00:00 30
08:00:02 2
08:03:00 10

Sample Output:

8.2

这题，测试点5需要注意的是假如有16:58:00 60 的数据和16:59:00 60的数据,16:58:00 60服务完理应是17:58:00,虽然已经超过了17:00:00，但银行并不关门，16:59:00 60的客户仍可以接受服务而不离开，最终应该在17:59:00关门。（我cnm，什么sb条件，卡了我一个下午。）

如果按照正常情况17:00:00之后还等待着的客户不提供服务，则加上代码里注释掉的部分。

 

#include <iostream>
#include <string>
#include <algorithm>
#include<math.h>
#include<queue>
#include<vector>

#define min_time 28800
#define max_time 61200

using namespace std;

int N=0;//客户数量
int K=0;//服务窗口数量
struct customer {
    int HH;
    int MM;
    int SS;
    int come;//c.HH * 60 * 60 + c.MM * 60 + c.SS
    int P;
}customers[10010];

int windows_pre[110];//每个窗口前一个人完成时间

int timetosec(customer c) {//时间化秒
    int sec = 0;
    sec = sec + c.HH * 60 * 60 + c.MM * 60 + c.SS;
    return sec;
}

int getavailablewin() {//最先空余窗口
    int time = windows_pre[1];
    int win = 1;
    for (int i = 2; i <= K; i++) {
        if (windows_pre[i] < time) {
            time = windows_pre[i];
            win = i;
        }
    }
    return win;
}

bool cmp(customer x, customer y) {
    return x.come < y.come;
}

int main() {
    cin >> N;
    cin >> K;
    int wait_time = 0;//等待时间
    for (int i = 1; i <= N; i++) {
        scanf("%d:%d:%d %d",
            &customers[i].HH,
            &customers[i].MM,
            &customers[i].SS,
            &customers[i].P);
        customers[i].come = timetosec(customers[i]);
        customers[i].P *= 60;
    }

    sort(customers + 1, customers + 1 + N, cmp);

    int available_person = N;
    for (int i = 1; i <= N; i++) {//come<28800为绝对等待时间,come>61200不需计算
        if (customers[i].come > max_time) {
            available_person = i - 1;
            break;
        }
        if (customers[i].come < min_time) {
            wait_time += (min_time - customers[i].come);
            customers[i].come = min_time;//所有人从8.后开始计算
        }
    }

    int count = available_person;//实际可服务人数
    if (available_person == 0) {//如果第一个人都无法服务
        count = 0;
        wait_time = 0;
    }
    else if (available_person <= K&& available_person > 1) {//客服务人数小于等于窗口数，则无需等待
        count = available_person;
        wait_time = wait_time;
    }
    else {//available_person > K
        for (int i = 1; i <= K; i++) {//初始化窗口
            windows_pre[i] = customers[i].come + customers[i].P;
        }
        for (int i = K + 1; i <= available_person; i++) {
            int availablewin = getavailablewin();
            //if (windows_pre[availablewin] >= max_time) {//如果队列中所有人完成时间都在17.后，那后面的人就不用排队了
            //count = i - 1;
            //break;
            //}
            if (customers[i].come < windows_pre[availablewin]) {
                wait_time += (windows_pre[availablewin] - customers[i].come);
                windows_pre[availablewin] += customers[i].P;
            }
            else {
                windows_pre[availablewin] = customers[i].come + customers[i].P;
            }
        }

        //int lastavailablewin = getavailablewin();
        //for (int j = count + 1; j <= available_person; j++) {//不用再排队的人也已经等了一会儿了
        //wait_time += (windows_pre[lastavailablewin] - customers[j].come);
        //}
    }

    if (count == 0) {
        printf("0.0");
    }
    else {
        printf("%0.1f", (double)wait_time / (60.0 * available_person));
    }
}