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甲級真題