PAT 1017 Queueing at Bank

题目描述

英文

中文大意

输入

N

个用户， 现有

K

个窗口，计算这些用户的平均等待时间

已知客户的 到达时间 和 需要的服务时间，按照先来先服务的原则进行服务

银行的服务时间为

08:00 - 17:00

，如果在

08:00

之前来了，就等到

08:00

，如果在

17-01

及之后来了，那就不能再被服务

样例

思路分析

构建一个

struct

来存储客户的 到来时间 和 服务时间，然后按照到来时间进行排序，此处用了

<algorithm> 的 sort 函数

。

然后参考 柳神的博客，维护了一个 优先队列(最小堆)，里面存放的是 窗口的业务完毕时间(也就是可以开始服务的时间)，此处把时间秒化 也是参照博客。

看到题目大概知道要用 优先队列，但是对

C++

的优先队列并不是很清楚，还有

vector

的用法也不太清楚。之后有时间会写个博客

易错点

cnt

：不能用

N

来计算，要单独使用

cnt

，把

17-00

以后的客户去掉

最后的输出不能写成

(double)total/(60)

，必须要用

60.0

code

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
#define MAX 10005
#define START_TIME 8 * 3600
#define END_TIME 17 * 3600

typedef struct person {
    int come, time;
};

int cmp(person p1, person p2) {
    return p1.come < p2.come;
}

/**
 * 17:00:01 = 61201
 * 08:00:00 = 28800
 * @return
 */
int main() {
    person p[MAX];  // 顾客队列
    int cnt = 0;    // 有效顾客数
    int total = 0;  // 总时间
    int N, K;       // N: 顾客数 K: 窗口数
    scanf("%d%d", &N, &K);
    for (int i = 0;i < N;i++) {
        // hh:mm:ss process
        int h, m, s, t, sum;
        scanf("%d:%d:%d %d", &h, &m, &s, &t);
        // 时间转换
        sum = h * 3600 + m * 60 + s;
        if (sum > END_TIME) continue;
        p[cnt].time = t * 60;
        p[cnt++].come = sum;
    }
    // 按到达时间进行排序比较
    sort(p, p + cnt, cmp);
    // 定义一个优先队列 (最小堆)
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0;i < K;i++)
        pq.push(START_TIME);
    for (int i = 0;i < cnt;i++) {
        // 窗口的最早可服务时间 <= 到来时间   即到来便可服务 无需等待
        // 初始化时已将最早可服务时间设置为 08:00
        if (pq.top() <= p[i].come) {
            // 该顾客的结束时间
            pq.push(p[i].come + p[i].time);
            pq.pop();
        } else {
            total += pq.top() - p[i].come;
            pq.push(pq.top() + p[i].time);
            pq.pop();
        }
    }
    (!cnt) ? printf("0.0") : printf("%.1lf", ((double)(total/60.0) / (double) cnt));
}

           

题目链接

1017 Queueing at Bank (25分)

参考文章

STL里的priority_queue用法总结

Queueing at Bank (25)-PAT甲级真题