习题8.2 银行排队问题之单队列多窗口加VIP服务 (30point(s))

假设银行有K个窗口提供服务，窗口前设一条黄线，所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时，下一位顾客即去该窗口处理事务。当有多个窗口可选择时，假设顾客总是选择编号最小的窗口。

有些银行会给VIP客户以各种优惠服务，例如专门开辟VIP窗口。为了最大限度地利用资源，VIP窗口的服务机制定义为：当队列中没有VIP客户时，该窗口为普通顾客服务；当该窗口空闲并且队列中有VIP客户在等待时，排在最前面的VIP客户享受该窗口的服务。同时，当轮到某VIP客户出列时，若VIP窗口非空，该客户可以选择空闲的普通窗口；否则一定选择VIP窗口。

本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间，并且统计每个窗口服务了多少名顾客。

Example

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

typedef struct CustomerType {
    int arrive;
    int process;
    int vip;
} *Customer;

typedef struct WindowType {
    int sum;
    int final;
    bool operator <(const WindowType &w) {
        return final < w.final;
    }
} *Window;

int main()
{
    int N;
    cin >> N;
    vector<CustomerType> c(N);
    vector<int>  used(N);
    for(int i = 0; i < N; i++) {
        cin >> c[i].arrive >> c[i].process >> c[i].vip;
        c[i].process = min(c[i].process, 60);
    }
    int K, vip;
    cin >> K >> vip;
    vector<WindowType> w(K);

    for(int i = 0; i < N; i++) {
        for(int h = 0; h < K; h++) {
            if(w[h].final < c.front().arrive) {
                w[h].final = c.front().arrive;
            }
        }
        int idle = 0;
        for(int h = 0; h < K; h++) {
            if(w[h].final < w[idle].final) {
                idle = h;
            } 
        }

        auto current = c.begin();
        for(auto cur = current; cur != c.end(); cur++) {
            if(cur->arrive > w[idle].final) break;
            else if(cur->vip) {
                if(w[vip].final == w[idle].final) {
                    current = cur;
                    idle = vip;
                }
                break;
            }
        }

        used[i] = w[idle].final - current->arrive;
        w[idle].sum++;
        w[idle].final += current->process;
        c.erase(current);
    }

    int longest = 0;
    int sum = 0;
    for(int i = 0; i < N; i++) {
        sum += used[i];
        if(used[i] > longest) longest = used[i];
    }
    auto latest = max_element(w.begin(), w.end());
    printf("%.1f %d %d\n", (double)sum/N, longest, latest->final);
    for(int h = 0; h < K; h++) {
        if(w[h].final > longest) longest = w[h].final;
    }
    for(int h = 0; h < K; h++) {
        cout << (h == 0 ? "" : " ") << w[h].sum;
    }
    return 0;
}

思路：

令窗口结束时间Final，大于等于对头的到达时间，然后找出结束时间最早的窗口，在检查顾客队列里有没有VIP在等待，如果有再检查是否vip也处于最早结束的一批窗口，如果时，就用Vip窗口服务Vip，若不是，就使用前面找到的窗口服务对头顾客。