PTA 7-6 银行排队问题之单队列多窗口加VIP服务

PTA 7-6 银行排队问题之单队列多窗口加VIP服务

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

否则一定选择VIP窗口。

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

这题比较恶心，可以通过模拟时间的流逝来进行暴力求解

#include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 1010;int n, m, v, window[maxn], cnt;struct Custom { int come, cost, vip, wait, finish;}custom[maxn];bool Time[20][maxn * 60], finish[maxn];void solve() { for (int t = 0; cnt < n; t++) { if (Time[v][t] == false) { for (int i = 1; i <= n; i++) { if (finish[i] == true || custom[i].vip == 0) continue; if (custom[i].come > t) break; finish[i] = true; custom[i].wait = t - custom[i].come; custom[i].finish = t + custom[i].cost; window[v]++; cnt++; for (int j = 0; j < custom[i].cost; j++) Time[v][t + j] = true; break; } } for (int i = 0; i < m; i++) { if (Time[i][t] == true) continue; for (int j = 1; j <= n; j++) { if (finish[j] == true) continue; if (custom[j].come > t) break; finish[j] = true; custom[j].wait = t - custom[j].come; custom[j].finish = t + custom[j].cost; window[i]++; cnt++; for (int k = 0; k < custom[j].cost; k++) Time[i][t + k] = true; break; } } } int sumwait = 0, maxwait = 0, finishtime = 0; for (int i = 1; i <= n; i++) { sumwait += custom[i].wait, maxwait = max(maxwait, custom[i].wait), finishtime = max(finishtime, custom[i].finish); } printf("%.1lf %d %d\n", 1.0 * sumwait / n, maxwait, finishtime); for (int i = 0; i < m; i++) printf("%d%c", window[i], i == m-1 ? '\n' : ' ');}int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d %d %d", &custom[i].come, &custom[i].cost, &custom[i].vip); if (custom[i].cost > 60) custom[i].cost = 60; custom[i].wait = custom[i].finish = 0; } scanf("%d %d", &m, &v); memset(window, 0, sizeof(window)); memset(Time, false, sizeof(Time)); memset(finish, false, sizeof(finish)); cnt = 0; solve(); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。