# PTA 7-6（队列） 银行排队问题之单队列多窗口加VIP服务（30 分） 3０分代码

xiaoxiao2021-02-28  16

VIP　题目　很恶心的

#include<bits/stdc++.h> using namespace std; const int maxn = 1000 + 7, INF = 0x7f7f7f7f; int n, k, vip; int b[11] = {0}; int cnt[11] = {0}; struct node { int t, p, vi; int len; } a[maxn]; bool vis[11][60*maxn] = {false}; bool viss[maxn] = {false}; void init() { scanf("%d", &n); for(int i = 0; i < n; ++i) { //scanf("%d %d %d", &a[i].t, &a[i].p, &a[i].vi); scanf("%d %d %d", &a[i].t, &a[i].p, &a[i].vi); //cout << a[i].t << ' ' << a[i].p << " " << a[i].vi << endl; if(a[i].p > 60) a[i].p = 60; } scanf("%d %d", &k, &vip); vip++; } void solve() { for(int i = 0; ; ++i ) { int ff = 1; for(int j = 0; j < n; ++j) { if(!viss[j]) ff = 0; } if(ff) break; if(!vis[vip][i]) { for(int j = 0; j < n; ++j) { if(!viss[j] && a[j].vi) { if(a[j].t <= i) { //cout << j << " ++++=====" << endl; viss[j] = true; a[j].len = i - a[j].t; for(int y = 0; y < a[j].p; ++y) vis[vip][i+y] = true; b[vip] = i + a[j].p; cnt[vip]++; break; } else break; } } } //cout << " === " << endl; for(int j = 1; j <= k; ++j) { if(!vis[j][i]) { for(int y = 0; y < n; ++y) { if(!viss[y]) {//cout << j << " " << y << " +++==="; if(a[y].t <= i) { viss[y] = true; a[y].len = i - a[y].t; for(int yy = 0; yy < a[y].p; ++yy) vis[j][i+yy] = true; b[j] = i + a[y].p; cnt[j]++; //cur = y+1; break; } else { //cur = y; break; } } } } } /*for(int c = 1; c <= k; ++c) cout << b[c] << " "; cout << endl << endl;*/ } //cout << " +++++++++" << endl; double ans1 = 0; int ans2 = 0, ans3 = 0; for(int i = 1; i <= k; ++i) { //cout << b[i] << " = " << endl; ans3 = max(ans3, b[i]); } int sum = 0; for(int i = 0; i < n; ++i) { //cout << a[i].len << " + " << endl;; ans2 = max(ans2, a[i].len); sum += a[i].len; } ans1 = (sum*1.0 / n*1.0); printf("%.1lf %d %d\n", ans1, ans2, ans3); for(int i = 1; i <= k; ++i) printf("%d%c", cnt[i], (i == k ? '\n' : ' ')); } int main() { init(); solve(); return 0; }