浙大版《数据结构（第2版）》题目集-习题8.2
习题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，若不是，就使用前面找到的窗口服务对头顾客。
赞 (0)