Suppose a bank has K 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 T and the processing time P of each customer, you are supposed to tell the average waiting time of all the customers.

假定银行有K个窗口进行服务，窗户前的黄线将等待区域分成两部分，所有的客户必须在黄线等待。直到他能等到服务为止，假设没有窗口能让顾客占据超过一小时。

Input Specification:
Each input file contains one test case. For each case, the first line contains 2 numbers: N (≤10 4
) - the total number of customers, and K (≤100) - the number of windows. Then N lines follow, each contains 2 times: HH:MM:SS - the arriving time, and P - 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.

输入规格：每个输入文件包含测试样例，针对每个样例，第一行包含两个数字，N代表顾客数，K是窗口数，接下来是N行，每个包含两个时间，HH::MM:Ss是抵达时间，P是顾客的处理时间，HH是到[00,23],MM和SS都是在00,59范围里，假设两个顾客没有想同的时间，注意，银行开始时间是8:00-17:00，任何人1来得早将会等你打底，以及任何人来晚也不能晚于17：00将不计入平均时间里。

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

核心思路

将银行的过程模拟出来。

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

struct customer{
    int come_time,process_time,leave_time = 0;
};
customer c[10001];

bool cmp(customer x,customer y){
    return x.come_time<y.come_time;
}
int main()
{
    int i,j,N,K;
    cin >> N >> K;
    for(i = 0;i<N;i++){
        int hh,mm,ss,process_time;
        char d;
        cin >> hh >> d >> mm >> d >> ss >> process_time;
        c[i].come_time = hh*3600+mm*60+ss;
        c[i].process_time = process_time*60;
        if(c[i].process_time>3600) c[i].process_time = 3600;
    }
    c[N].come_time = 9999999;
    sort(c,c+N,cmp);
    int next = 0;
    double sum = 0;
    int window[K];
    for(i = 0;i<K;i++) window[i] = -1;
    for(int Time = 28800;c[next].come_time<=61200;Time++){
        for(i=0;i<K;i++){
            if(window[i]>=0){
                j=window[i];
                if(c[j].leave_time ==Time ){
                    window[i] = -1;
                }
            }
        }
        //送客
        for(i=0;i<K;i++){
            if(window[i] == -1){
                if(c[next].come_time<= 61200 && c[next].come_time <= Time){
                    window[i]= next;
                    next++;
                }
            }
        }
        //入队
        for(i=0;i<K;i++){
            if(window[i] >= 0){
                j = window[i];
                if(c[j].leave_time == 0){
                    sum += Time-c[j].come_time;
                    c[j].leave_time = Time+c[j].process_time;
                }
            }
        }
        //映客
    }
    printf("%.1f",sum/next/60);
    return 0;
}

方法2

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int K = 111;
const int INF = 1e9;
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];
int main(){
    int c,w,totTime = 0;
    int stTime = convertTime(8,0,0);
    int edTime = convertTime(17,0,0);
    scanf("%d%d",&c,&w);
    for(int i =0;i<w;i++) endTime[i] = stTime;
    for(int 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;
        custom.push_back(newCustomer);
    }
    sort(custom.begin(),custom.end(),cmp);
    for(int 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;
            }
        }
        if(endTime[idx] <= custom[i].comeTime){
            endTime[idx] = custom[i].comeTime + custom[i].serveTime;
        }else{
            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;
}