小思路

• 先把每个人排序，然后一个人一个人看，找最小的窗口放这个人。

• 用户等待时间 = 开始服务时间 - 到达时间

  • 那么时候开始服务：两种情况

    1. 当用户到了时，窗口没人，那就直接开始服务：person.arrive_time

    2. 当用户到了时，窗口有人，那就得等窗口完事你才能开始：windows.top()

• 最小的窗口，这里使用了小根堆来维护窗口priority_queue<int, vector<int>, greater<int>> windows; 每次top()返回最小值

• 如何更新窗口：新的窗口值 = 开始服务时间 + 服务时间

小知识点

• 在这里仍然是把时间转换成距离0点的秒数，方便计算！技巧！

  （所以要记得初始化窗口从八点开始）

• 对结构体排序，就要在结构体里重载运算符

注意

• “已经办理了一小时，则立即终止此项业务”，即：服务时间不得超过60min:

  service_time = min(service_time, 60);

• “任何人来得太晚都将不被服务”：(y总说来晚了让他gun，笑死了hhh)

  if (person.arrive_time > 17 * 3600) break;

• 最小的窗口每次要弹出最小的数，一定记得加greater<int>变成小根堆

• 记得要对人计数，不是所有人都可以被服务到

• 每次的最小窗口用完记得pop()掉

code

#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;

const int N = 1e4 + 10, M = 110;

int n, m;

struct Person
{
    int arrive_time;
    int service_time;

    // 对结构体排序，就要在结构体里重载运算符！！！
    bool operator< (const Person& t) const
    {
        return arrive_time < t.arrive_time;
    }

}persons[N];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
    {
        int hour, minute, second,service_time;
        scanf("%d:%d:%d %d", &hour, &minute, &second, &service_time);

        // 服务时间不得超过60min:已经办理了一小时，则立即终止此项业务
        service_time = min(service_time, 60);


        persons[i] = {hour * 3600 + minute * 60 + second, service_time * 60}; 
    }

    priority_queue<int, vector<int>, greater<int>> windows;  
    for (int i = 0; i < m; i ++ ) windows.push(8 * 3600);  // 初始化窗口，从早八点开始

    // 对人来的顺序进行排序
    sort(persons, persons + n);

    int wait_time = 0, cnt = 0;
    for (int i = 0; i < n; i ++ ) 
    {
        // 对于第i个人
        auto person = persons[i];
        if (person.arrive_time > 17 * 3600) break;

        int w = windows.top();  // 窗口最小值
        windows.pop();  // 用了窗口最小值就把他删掉


        // 开始服务时间
        int start_time = max(person.arrive_time, w);

        // 在窗口等待时间 = 开始服务时间 - 到达时间
        wait_time += start_time - person.arrive_time;
        cnt ++;

        windows.push(start_time + person.service_time);
    }

    printf("%.1lf\n", (double)wait_time / cnt / 60);

    return 0;
}

新手学的比较吃力，如果有错误欢迎您指出！！！