浙大 PAT 甲級 1017 Queueing at Bank C++

思路

跟1014題很像，也是一道模拟排隊題。差別在于1014側重單入口多出口的排隊，預設所有人都在開始時刻開始排隊，而1017題黃線前的若幹條隊伍每隊隻能容納1人，并且考慮不同時刻的到達。

資料結構考慮一個結構體Customer代表排隊的人，兩個成員變量：到達時間、業務辦理所需時長。用一個vector<Custmoer>代表隊列，sort函數(#include<algorithm>)使其按照到達時間排序即可。還有一個整型數組，下标代表視窗編号，其值代表每個視窗恢複空閑的時刻，最開始為八點，過程中為占用這個視窗的使用者的到達時間加上其業務所需時長。

以上是大緻思路，還有兩個細節需要考慮：

• 17:00及以後到達的，不能加入vector，直接忽略即可。
• 8:00以前到達的，如果把算法寫的具有普遍性，那麼這一點就完全不需要考慮。我的做法是，定義一個标記變量bool nowait，把客戶分成經曆了等待時間的，和未經曆等待時間的，分别處理，這樣算法就可能會簡單一些。

代碼

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

struct Customer
{
    int atime;
    int ptime;
};
vector<Customer> lines;
int windows[100];

bool cmp(Customer a, Customer b)
{
    return a.atime < b.atime;
}

int main()
{
    int N, K;
    scanf("%d%d", &N, &K);
    for (int i = 0; i < N; i++)
    {
        int h, m, s, p;
        scanf("%d:%d:%d%d", &h, &m, &s, &p);
        Customer c;
        c.atime = h * 3600 + m * 60 + s;
        c.ptime = p;
        if (c.atime < 17 * 3600)
        {
            lines.push_back(c);
        }
    }
    for (int i = 0; i < K; i++)
    {
        windows[i] = 8 * 3600;
    }
    sort(lines.begin(), lines.end(), cmp);
    float sum = 0;
    for (int i = 0; i < lines.size(); i++)
    {
        bool nowait = false;
        int min = 10000000;
        int w = -1;
        for (int j = 0; j < K; j++)
        {
            if (windows[j] < lines[i].atime)
            {
                windows[j] = lines[i].atime + lines[i].ptime * 60;
                nowait = true;
                break;
            }
            if (windows[j] < min)
            {
                min = windows[j];
                w = j;
            }
        }
        if (!nowait)
        {
            sum += windows[w] - lines[i].atime;
            windows[w] += lines[i].ptime * 60;
        }
    }
    printf("%.1f", sum / 60.0 / (float)lines.size());
    return 0;
}