C++
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 10010, K = 110;
int window[K];
struct Person
{
int arrive_time;
int op_time;
int served_time = 0x3f3f3f3f;
bool operator<(const Person& A) { //sort naturally according to arrive time
return arrive_time < A.arrive_time;
}
} client[N];
int n, k; //num of customers and windows
int hour, minute, second;
char time_str[15];
//because no customer arrives at the same time, only maximum 1 customer can come to a window at one timestamp
int convert_second(int h, int m, int s) //convert format time to all_seconds since 00:00
{
return h * 3600 + m * 60 + s;
}
int main()
{
memset(window, -1, sizeof (window));
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++ ) {
scanf("%02d:%02d:%02d", &hour, &minute, &second);
sprintf(time_str, "%02d:%02d%:02d", hour, minute, second);
int second_stamp = convert_second(hour, minute, second);
client[i].arrive_time = second_stamp;
scanf("%d", &client[i].op_time); //convert op minute to seconds, maximum is 1 hour(3600s)
client[i].op_time = min(client[i].op_time * 60, 3600);
}
sort(client, client + n);
client[n].arrive_time = 0x3f3f3f3f; //in case of all customer come before 17:00, add a virtual customer to make sure the for loop will end
int wait_sum = 0; //sum all waiting times, unit(s)
int cid = 0; //num of customers that accepted service
for (int this_time = 8 * 3600; client[cid].arrive_time <= 17 * 3600; this_time++ ) { //as long as a customer comes <= 17:00, he will get service
for (int i = 0; i < k; i++ ) { //check if any client finishes his serve
int id = window[i]; //locate who is the client severd at window i
if (id != -1) { //window[i] has a client
Person cp = client[id];
if (this_time >= cp.served_time + cp.op_time) { //service finished
window[i] = -1; //window i has no client now
}
}
}
for (int i = 0; i < k; i++ ) { //check if a client can be served at this time
if (window[i] == -1) {
if (this_time >= client[cid].arrive_time and client[cid].arrive_time <= 17 * 3600) {
client[cid].served_time = this_time; //client cid can serve at window i
wait_sum += this_time - client[cid].arrive_time; //the waiting time of this customer can be computed
window[i] = cid++ ; //record window i and iterate cid
}
}
}
}
// cout << wait_sum << endl;
// // cout << finish_time << endl;
// for (int i = 0; i < n; i++ ) {
// cout << client[i].arrive_time << " " << client[i].served_time << " " << client[i].served_time - client[i].arrive_time << endl;
// }
double wait_minute = (double)wait_sum / 60.0; //convert to unit(minute)
wait_minute /= cid; //cal average
printf("%.1lf", wait_minute);
return 0;
}