解题思路：
基本原理为一队多窗口问题，利用模拟队列进行操作
step:
①通过每个人来到的时间与窗口结束上一个工作的时间的关系来进行插入预备队列：
每次插入一个人，进行一次预备队列的刷新，即获得结束时间最小的窗口的时间，将所有输入中由头至尾将客户的到达时间小于该结束时间的客户进行入队（预备队列即排队）
②对预备队列进行操作：
1.若队列中有VIP且此时VIP窗口结束则将VIP客户安排到VIP窗口
2.获得最早结束的窗口时间，若该时间与VIP窗口同时结束，且队伍中有VIP客户，则先将VIP客户安排到VIP窗口，再安排从预备队列的头部进行安排
3.若预备队列为空，且工作未结束表明，下一个客户来到时候可以直接安排到窗口无需等待，此时只需判断此客户是否为VIP和VIP窗口是否为空即可.
4.若获得的最早结束的窗口不是VIP窗口且VIP窗口结束时间不等于最早结束窗口，则进行正常的按规则安排，特别注意无论此时队首是不是VIP此时都对窗口安排无关，但需在编程时注意VIP的操作控制.
代码实现：
#include<iostream> #include<cstdio> #include<queue> using namespace std; class People{ //客户 public: People(){ arrive = 0; time = 0; vip = 0; use = 0; } public: int arrive; int time; int vip; int use; //该客户是否已被操作 }; People p[10000]; int win[20]; //每个窗口的最后结束时间 int k; int t = 0; int VIP; //VIP窗口 int sum[20] = {0};//每个窗口的客户人数 int wait[10000]; //每个让客户的等待时间 int flag = 0; //队列中VIP存在的数目 queue<int> pos; //存放队列中VIP的下标 int getmin(){ int min = win[0]; int key = 0; for(int i = 0;i < k;i++) { if(min > win[i]){ key = i; min = win[i]; } } return key; } int getmax(){ int max = 0; for(int i = 0;i < k;i++){ if(max < win[i])max = win[i]; } return max; } int main(){ int n,j,i; cin>>n; int min = 0; int num = n; int tail = 0; //对所有人操作的头索引 int head = 0; //对所有人操作入队的尾索引 for(i = 0;i < n;i++){ cin>>p[i].arrive>>p[i].time>>p[i].vip; if(p[i].time > 60)p[i].time = 60; } cin>>k>>VIP; if(n != 0) while(num){ int key = getmin(); while(tail <= n){ //根据从最早结束的窗口的时间和客户到达的时间进行入队 while(p[tail].use == 1 && tail <= n)tail++; if(p[tail].arrive < win[key] && tail <= n){ if(p[tail].vip == 1){ flag++; pos.push(tail); } tail++; } else break; } while(p[head].use == 1)head++; //对已操作的客户进行过滤 if(head == tail){ //头索引 == 尾索引表明此时队列为空，下一个客户直接插入 for(j = 0;j < k;j++) if(win[j] <= p[head].arrive)break; if(p[head].vip == 1 && p[head].arrive >= win[VIP] && flag == 0)j = VIP; win[j] = p[head].arrive + p[head].time; sum[j]++; p[head].use = 1; head++; tail++; num--; continue; } else{ if((key == VIP && flag > 0 )|| (win[key] == win[VIP] && flag > 0)){ //当VIP窗口闲置且队伍中存在VIP时对VIP的安排 int k = pos.front(); pos.pop(); wait[k] += (win[VIP] - p[k].arrive); if(wait[k] > min)min = wait[k]; win[VIP] += p[k].time; sum[VIP]++; p[k].use = 1; flag--; num--; } else{ //当不满足VIP安排时，正常的对队首的安排，此时安排无关是否为VIP. wait[head] += (win[key] - p[head].arrive); if(wait[head] > min)min = wait[head]; win[key] += p[head].time; p[head].use = 1; if(p[head].vip == 1 && flag > 0){ //若是VIP需将从pos的VIP下标队列中删除 flag--; pos.pop(); } sum[key]++; head++; num--; } } } //格式化输出 if(n == 0){ cout<<"0.0 0 0"<<endl; } else{ for(i = 0;i < n;i++) t += wait[i]; double avg = (double)(1.0 * t / n); printf("%.1lf " , avg); cout<<min<<" "; int max_time = getmax(); cout<<max_time<<endl; } for(i = 0;i < k;i++) if(i == 0)cout<<sum[i]; else cout<<" "<<sum[i]; }
