PAT1017. Queueing at Bank

試題請參見: http://pat.zju.edu.cn/contests/pat-a-practise/1016

題目概述

假設有N個客戶在K個視窗等待服務。 每個視窗可以容納一個人, 是以其他客戶需要進行等待. 當某個客戶服務完成後, 下一個客戶可以進入該視窗并被服務. 我們假設沒有視窗會被占用1小時以上.

現在我們給出每個客戶的到達時間T和服務該客戶所需要的時間P, 請計算所有客戶的平均等待時間.

輸入

每個輸入檔案包含一個測試用例. 每個測試用例, 第一行包含兩個整數N( <= 1000)和K( <= 100). 其中N表示客戶的數量, K表示視窗的數量. 接下來的N行, 包含兩個時間: HH:MM:SS, 表示客戶的到達時間; P, 表示服務該客戶所需要的時間(以分鐘為機關). HH的範圍是[00, 23], MM和SS的範圍是[00, 59]. 我們假設沒有兩個客戶在同一時間到達.

需要說明的是, 銀行的營業時間是08:00-17:00. 如果到達的時間早于08:00, 客戶需要等待至銀行開始營業才能被服務; 如果客戶晚于(或恰好在)17:00:01到達銀行, 則該客戶不會被服務, 是以也無需計算該客戶的平均等待時間.

輸出

對于每一個測試用例, 請輸出客戶的平均等待時間, 以分鐘為機關, 并精确到一位小數.

解題思路

典型的模拟題, 并且比PAT 1014要簡單一點的模拟題.

讀入資料時, 自動過濾17:00:00以後到達的客戶.

按客戶先後到達順序進行服務,  在客戶服務完成後,  更新視窗的服務完成時間.

客戶每次選擇服務完成時間最短的進行排隊(服務).

需要考慮如下情況: 

- 若銀行未營業, 則客戶需要等待;

(以及在“遇到的問題”中闡述的一些情況)

遇到的問題

若幹次WA, 存在如下需要考慮的情況

1. 若所有顧客都在17:00:00以後到達, 則結果為0.0; 2. 若目前所有顧客都已服務完畢, 但是下一位顧客還未到來, 需要視窗需要等待; 3. 若目前客戶不需要等待, 則該視窗服務完成時間時為客戶到達時間 + 服務時間; 否則, 該視窗服務完成時間為上一個客戶完成的時間 + 該客戶服務時間.

源代碼

#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <string>
#include <vector>

const std::string BANK_OPEN_TIME = "08:00:00";
const std::string BANK_CLOSE_TIME = "17:00:00";

struct Customer {
    std::string arrivedTime;
    int waitingTime;      // seconds
    int processingTime;   // seconds
    
    Customer() {
        waitingTime = 0;
        processingTime = 0;
    }
};

struct Window {
    int currentTime;      // seconds

    Window() {
        currentTime = 0;
    }
};

int atoi(char timeDigit0, char timeDigit1) {
    return (timeDigit0 - '0') * 10 + (timeDigit1 - '0');
}

int getIntervalBetweenTime(const std::string& startTime, const std::string& endTime) {
    if ( startTime >= endTime ) {
        return 0;
    }

    int startHour = atoi(startTime[0], startTime[1]);
    int startMinute = atoi(startTime[3], startTime[4]);
    int startSecond = atoi(startTime[6], startTime[7]);
    int endHour = atoi(endTime[0], endTime[1]);
    int endMinute = atoi(endTime[3], endTime[4]);
    int endSecond = atoi(endTime[6], endTime[7]);

    int interval = (endHour - startHour) * 3600 + (endMinute - startMinute) * 60
                 + (endSecond - startSecond);
    return interval;
}

int getIntervalBetweenTime(const std::string& startTime, int endTime) {
    int startHour = atoi(startTime[0], startTime[1]);
    int startMinute = atoi(startTime[3], startTime[4]);
    int startSecond = atoi(startTime[6], startTime[7]);
    int interval = endTime - ((startHour - 8) * 3600 + startMinute * 60 + startSecond);


    return (interval > 0 ? interval : 0);
}

int getCustomerCompleteTime(std::string& arrivedTime, int processingTime) {
    if ( arrivedTime < BANK_OPEN_TIME ) {
        arrivedTime = BANK_OPEN_TIME;
    }
    int arrivedHour = atoi(arrivedTime[0], arrivedTime[1]);
    int arrivedMinute = atoi(arrivedTime[3], arrivedTime[4]);
    int arrivedSecond = atoi(arrivedTime[6], arrivedTime[7]);
    int completeTime = (arrivedHour - 8) * 3600 + arrivedMinute * 60 + arrivedSecond + processingTime;

    return completeTime;
}

bool customerCompare(const Customer& customer1, const Customer& customer2) {
    return customer1.arrivedTime < customer2.arrivedTime;
}

int main() {
    // std::ifstream cin;
    // cin.open("input.txt");
    using std::cin;

    int n = 0, k = 0;
    cin >> n >> k;

    std::vector<Customer> customers;
    std::vector<Window> windows(k);

    // Input
    for ( int i = 0; i < n; ++ i ) {
        Customer customer;
        cin >> customer.arrivedTime >> customer.processingTime;
        if ( customer.arrivedTime <= BANK_CLOSE_TIME ) {
            customer.processingTime *= 60;
            customers.push_back(customer);
        }
    }

    // Processing
    std::sort(customers.begin(), customers.end(), customerCompare);
    size_t customerIndex = 0;
    for ( ; customerIndex < k && customerIndex < customers.size(); ++ customerIndex ) {
        Customer& customer = customers[customerIndex];
        Window& window = windows[customerIndex];
        customer.waitingTime = getIntervalBetweenTime(customer.arrivedTime, BANK_OPEN_TIME);
        window.currentTime += getCustomerCompleteTime(customer.arrivedTime, customer.processingTime);
    }

    for ( ; customerIndex < customers.size(); ++ customerIndex ) {
        int firstCompleteWindowIndex = 0, firstCompleteWindowTime = 1 << 30;
        // Search for a window to serve
        for ( size_t i = 0; i < windows.size(); ++ i ) {
            if ( windows[i].currentTime < firstCompleteWindowTime ) {
                firstCompleteWindowTime = windows[i].currentTime;
                firstCompleteWindowIndex = i;
            }
        }
        Customer& customer = customers[customerIndex];
        Window& window = windows[firstCompleteWindowIndex];
        customer.waitingTime = getIntervalBetweenTime(customer.arrivedTime, window.currentTime);
        int completeTime = getCustomerCompleteTime(customer.arrivedTime, customer.processingTime);
        if ( customer.waitingTime == 0 ) {
            window.currentTime = completeTime;
        } else {
            window.currentTime += completeTime;
        }
    }

    // Output
    double averageWaitTime = 0;
    for ( size_t i = 0; i < customers.size(); ++ i ) {
        averageWaitTime += customers[i].waitingTime;
    }
    if ( customers.size() != 0 ) {
        averageWaitTime /= customers.size() * 60;
    }

    std::cout << std::fixed << std::setprecision(1) << averageWaitTime << std::endl;

    return 0;
}