PAT 甲級 1017. Queueing at Bank

原題傳送門

• 題意：有N個客戶，K個視窗。已知每個客戶的到達時間和需要的時長（不超過60min，超過的會被壓縮成60min），如果有視窗就依次過去，如果沒有視窗就在黃線外等候（黃線外隻有一個隊伍，先來先服務），求客戶的平均等待時長（十進制，機關：分鐘）。銀行開放時間為8點到17點，再8點之前不開門，8點之前來的人都要等待，在17點後來的人不被服務。
• < algorithm >中sort()對vector進行排序
• 讀取标準時間用scanf()
• 精确到秒，先全部轉化為秒來計算

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

struct node {
    int come, time;
} customer;

bool cmp1(node a, node b) {
    return a.come < b.come;
}

int main(int argc, const char * argv[]) {
    int N, K;
    cin >> N >> K;
    vector<node> line;
    for(int i = ; i < N; ++i) {
        int hour, minute, second, time;
        scanf("%d:%d:%d %d", &hour, &minute, &second, &time);
        if(time > )
            time = ;
        int cometime = hour *  + minute *  + second;
        if(cometime > (**)) // 17點
            continue;
        customer.come = cometime;
        customer.time = time * ;
        line.push_back(customer);
    }
    sort(line.begin(), line.end(), cmp1);
    vector<int> window(K, (**)); // 存儲各視窗的結束時間，大小為K，初始化為8點
    double result = ;
    for(int i = ; i < line.size(); ++i) {
        int index = ; // 視窗号
        int minfinish = window[]; // 各視窗中的最早結束時間

        // 循環檢查各視窗，如果有視窗結束時間更早，則更新最早結束時間和視窗号：
        for(int j = ; j < K; ++j) {
            if(minfinish > window[j]) {
                minfinish = window[j];
                index = j;
            }
        }

        // 确定下一個服務的視窗号和時間後：與客戶到達時間進行比較
        if(window[index] <= line[i].come) { // 如果在客戶到達之前，客戶無等待
            window[index] = line[i].come + line[i].time;
        } else { // 在客戶到達之後，更新等待時間result
            result += (window[index] - line[i].come);
            window[index] += line[i].time;
        }
    }
    if(line.size() == )
        printf("0.0");
    else
        printf("%.1f", result /  / line.size());

    return ;
}
           

附原題：

Suppose a bank has K windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. All the customers have to wait in line behind the yellow line, until it is his/her turn to be served and there is a window available. It is assumed that no window can be occupied by a single customer for more than 1 hour.

Now given the arriving time T and the processing time P of each customer, you are supposed to tell the average waiting time of all the customers.

• Input Specification:

Each input file contains one test case. For each case, the first line contains 2 numbers: N (<=10000) - the total number of customers, and K (<=100) - the number of windows. Then N lines follow, each contains 2 times: HH:MM:SS - the arriving time, and P - the processing time in minutes of a customer. Here HH is in the range [00, 23], MM and SS are both in [00, 59]. It is assumed that no two customers arrives at the same time.

Notice that the bank opens from 08:00 to 17:00. Anyone arrives early will have to wait in line till 08:00, and anyone comes too late (at or after 17:00:01) will not be served nor counted into the average.

• Output Specification:

For each test case, print in one line the average waiting time of all the customers, in minutes and accurate up to 1 decimal place.

• Sample Input:

  7 3

  07:55:00 16

  17:00:01 2

  07:59:59 15

  08:01:00 60

  08:00:00 30

  08:00:02 2

  08:03:00 10

• Sample Output:

  8.2