7-5 银行排队问题之单队列多窗口加VIP服务 (8分) 假设银行有K个窗口提供服务，窗口前设一条黄线，所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时，下一位顾客即去该窗口处理事务。当有多个窗口可选择时，假设顾客总是选择编号最小的窗口。
有些银行会给VIP客户以各种优惠服务，例如专门开辟VIP窗口。为了最大限度地利用资源，VIP窗口的服务机制定义为：当队列中没有VIP客户时，该窗口为普通顾客服务；当该窗口空闲并且队列中有VIP客户在等待时，排在最前面的VIP客户享受该窗口的服务。同时，当轮到某VIP客户出列时，若VIP窗口非空，该客户可以选择空闲的普通窗口；否则一定选择VIP窗口。
本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间，并且统计每个窗口服务了多少名顾客。 输入格式:
输入第1行给出正整数N（≤1000），为顾客总人数；随后N行，每行给出一位顾客的到达时间T、事务处理时间P和是否VIP的标志（1是VIP，0则不是），并且假设输入数据已经按到达时间先后排好了顺序；最后一行给出正整数K（≤10）—— 为开设的营业窗口数，以及VIP窗口的编号（从0到K−1）。这里假设每位顾客事务被处理的最长时间为60分钟。 输出格式:
在第一行中输出平均等待时间（输出到小数点后1位）、最长等待时间、最后完成时间，之间用1个空格分隔，行末不能有多余空格。
在第二行中按编号递增顺序输出每个窗口服务了多少名顾客，数字之间用1个空格分隔，行末不能有多余空格。 输入样例：
10 0 20 0 0 20 0 1 68 1 1 12 1 2 15 0 2 10 0 3 15 1 10 12 1 30 15 0 62 5 1 3 1
输出样例：
15.1 35 67 4 5 1 理解： 1.队列在随时间不断变化， 是以时间为天然的序 2.vip可以插队，vip在一个队列时如果有vip柜台空闲那么vip人员不管在队列中那个位置都直接去办理业务 思路：可以以时间为天然的序， 来进行处理，但要注意vip与vip柜台的对应 思考：对于这种大模拟，我们最好在开始时，进行模拟一次，理解模拟规则， 再按照某个方向进行模拟，而本题中直接就有时间这个序，可以直接for(int i = 0; i ; i ++)循环 在我的代码中对该方法进行了优化，使其不会循环不会使用的时间点， 但也导致使用了太多的STL容器， 其结果并不见得优化了多少
#include<bits/stdc++.h> using namespace std; const int N = 1101; int n, k, vip_adress = 0, num[N], max_wait, last_complete, vis[N];//标记是否已经被服务 double all_wait; struct node { int arrive_time; int solve_time; bool vis; }customers[N]; struct counter { int id; int start; int end_time; bool operator <(const counter &x)const { if(end_time != x.end_time) return end_time > x.end_time; return id > x.id; } }counters[11]; priority_queue<counter> q;//优先队利存储柜台 void get_ans(int x, int y) // 将第y个人放入第x个柜台 { counters[x].start = max(customers[y].arrive_time, counters[x].end_time); counters[x].end_time = counters[x].start + customers[y].solve_time; int x1 = counters[x].start - customers[y].arrive_time; num[x] ++; max_wait = max(x1, max_wait); last_complete = max(last_complete, counters[x].end_time); all_wait += x1; } int main() { cin >> n; for(int i = 1; i <= n; i++) { cin >> customers[i].arrive_time >> customers[i].solve_time >> customers[i].vis; customers[i].solve_time = customers[i].solve_time > 60?60:customers[i].solve_time; } cin >> k >> vip_adress; vip_adress ++;//(0, k - 1) for(int i = 1; i <= k; i++) { counters[i].id = i; q.push(counters[i]); } int rear = 1, pre = 1; //创建队列 while(rear <= n) { int x = q.top().id; vector<counter> qual; // 找当前可能用到的柜台 bool flag1 = false;//判断相同时间内有无空闲的vip房间 while(vis[rear] == 1) rear ++;//在队列中还没有完成的人的 while(pre <= n && counters[x].end_time >= customers[pre].arrive_time) pre ++;// 更新有多少人放入队列 if(rear >= pre) pre = rear + 1; // 到达终点rear -> n if(rear > n) break; while(q.size() > 0 && (q.top().end_time == counters[x].end_time && counters[x].end_time >= customers[rear].arrive_time) || (counters[x].end_time <= customers[rear].arrive_time && q.top().end_time <= customers[rear].arrive_time)) //将可能用到的柜台放入数组 {//找可能使用的柜台时间相等时，还要注意vip房间 //1如果当前的第一个可能使用的人的到达时间小于最早结束时间， 后序相等的柜台都进 //2如果当前的第一个人到达的时间大于柜台最早结束的时间， 那么在他到达之前的时间内空闲的柜台都进 qual.push_back(q.top()); if(q.top().id == vip_adress) { flag1 = true;//标记是否有vip柜台 q.pop(); break; } q.pop(); } if(counters[x].end_time < customers[rear].arrive_time) //当前的第一个人到达的时间大于柜台最早结束的时间 { while(pre <= n && customers[pre].arrive_time == customers[rear].arrive_time) // 更新所有相等的人 pre ++; } bool flag = false; int id_vip = 0; for(int i = rear; i < pre; i++)//判断有无vip人 if(customers[i].vis && vis[i] == 0) { id_vip = i, flag = true; break; } if(flag1 && flag)//如果是vip且该房间是vip房间 { get_ans(vip_adress, id_vip); for(int i = 0; i < qual.size() - 1; i++) q.push(qual[i]); q.push(counters[vip_adress]); vis[id_vip] = 1; } else { if(rear <= n) { get_ans(x, rear); for(int i = 1; i < qual.size(); i++) q.push(qual[i]); q.push(counters[x]); vis[rear] = 1; rear ++; } else break; } } printf("%.1f %d %d\n", all_wait/n, max_wait, last_complete); for(int i = 1; i <= k; i++) printf("%d%c", num[i], i == k ? '\n':' '); return 0; }