PAT 1017 Queueing at Bank (25分) prioriry_queue

  // 定义：priority_queue<Type, Container, Functional>
  //  Type 就是数据类型，Container 就是容器类型
  // （Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），
  // Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型
  // 默认是大顶堆

  //升序队列
  priority_queue <int,vector<int>,greater<int> > q;
  //降序队列
  priority_queue <int,vector<int>,less<int> >q;

  // greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。
  // 其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

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

struct People {
    // 全部以秒为单位进行记录
    int arrive_time, process_time;
} people[10000];

// 用于升序排序
bool cmp(People c1, People c2) {return c1.arrive_time < c2.arrive_time;} 

int main() {
    // 银行开始服务时间，结束服务时间
    int bank_open_time = 8 * 3600, bank_close_time = 17 * 3600;
    // n 个人，k 个窗口
    int n, k;
    cin >> n >> k;
    // 记录有效的，被服务的客户数目
    int index = 0;
    // 所有被服务的客户的等待时间
    int total_wait_time = 0;
    int h, m, s, p;
    for (int i = 0; i < n; ++i) {
        scanf("%d:%d:%d %d", &h, &m, &s, &p);
        int time = h * 3600 + m * 60 + s;
        // 在 17:00之后到达，不会被服务，不用记录，不用于计算平均时间
        if (time > bank_close_time) continue;
        // 保存这个客户记录，index+=1
        people[index].arrive_time = time;
        if (p > 60) p = 60; // 每个窗口服务不会超过1小时，相当于把他的占用时间改为1小时
        people[index].process_time = p * 60;
        index++;
    }
    // 根据到达时间进行排序
    sort(people, people + index, cmp);
    // 用一个优先队列维护k个窗口当前服务结束时间，使用小顶堆
    // 第二个参数必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector
    // greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）
    // 默认实现的是大顶堆
    priority_queue<int, vector<int>, greater<int>> minheap;
    // 首先k个窗口都是8:00开始服务，相当于它当前服务的结束时间都是8:00
    while (k-- > 0)
        minheap.push(bank_open_time);
    // 顾客已经排好序了，逐个处理
    for (int i = 0; i < index; ++i) {
        // 最早结束服务的那个窗口服务在他来之前能够结束服务，甚至可能已经空了一会
        if (minheap.top() <= people[i].arrive_time) {
            // 不用等待
            // pop()相当于那个窗口结束上一个服务
            // 接着窗口为他服务，那么这个窗口这次的结束时间就是 【这个人来的时间+这个人需要的时间】
            minheap.push(people[i].arrive_time + people[i].process_time);
            // 本应该先结束服务再为他服务，但先pop()栈顶元素改变，我们得先保存top()
            minheap.pop();
        } else {
            // 他需要等 最早的那个窗口结束当前服务
            total_wait_time += minheap.top() - people[i].arrive_time;
            // 然后窗口结束服务，为他服务，最小堆pop()并插入新元素
            // 这里与上面的区别的是，窗口这次的结束时间是 【窗口上次的结束时间+这个人的等待时间】
            minheap.push(minheap.top() + people[i].process_time);
            // 本应该先结束服务再为他服务，但先pop()栈顶元素改变，我们得先保存top()
            minheap.pop();
        }
    }
    // 以分钟输出平均等待时间
    printf("%.1f", total_wait_time / 60.0 / index);

    return 0;
}