7-4 银行排队问题之单窗口“夹塞”版

网友投稿 1040 2022-11-28

7-4 银行排队问题之单窗口“夹塞”版

7-4 银行排队问题之单窗口“夹塞”版

排队“夹塞”是引起大家强烈不满的行为，但是这种现象时常存在。在银行的单窗口排队问题中，假设银行只有1个窗口提供服务，所有顾客按到达时间排成一条长龙。当窗口空闲时，下一位顾客即去该窗口处理事务。此时如果已知第i位顾客与排在后面的第j位顾客是好朋友，并且愿意替朋友办理事务的话，那么第i位顾客的事务处理时间就是自己的事务加朋友的事务所耗时间的总和。在这种情况下，顾客的等待时间就可能被影响。假设所有人到达银行时，若没有空窗口，都会请求排在最前面的朋友帮忙（包括正在窗口接受服务的朋友）；当有不止一位朋友请求某位顾客帮忙时，该顾客会根据自己朋友请求的顺序来依次处理事务。试编写程序模拟这种现象，并计算顾客的平均等待时间

#include #include #include #include #include #include #include #include using namespace std;const int maxn = 1e4 + 10;map ID;struct Data { string name; int come, cost;}data[maxn];int main() { int n, m; string s; vector friends[maxn]; map belong; cin >> n >> m; for (int i = 1; i <= m; i++) { int l; cin >> l; for (int j = 1; j <= l; j++) { cin >> s; belong[s] = i; friends[i].push_back(s); } } int come, cost; for (int i = 1; i <= n; i++) { cin >> s >> come >> cost; ID[s] = i; data[i].name = s, data[i].come = come, data[i].cost = cost > 60 ? 60 : cost; } int bel[maxn]; vector fri[maxn]; for (int i = 1; i <= m; i++) { for (int j = 0; j < friends[i].size(); j++) { int x = ID[friends[i][j]]; bel[x] = i; fri[i].push_back(x); } sort(fri[i].begin(), fri[i].end()); } bool vis[maxn]; memset(vis, false, sizeof(vis)); queue q; int time = 0; double ans = 0; for (int i = 1; i <= n; i++) { if (vis[i]) continue; vis[i] = true; if (data[i].come >= time) time = data[i].come + data[i].cost; else { ans += time - data[i].come; time += data[i].cost; } q.push(i); int group = bel[i]; for (int j = 0; j < fri[group].size(); j++) { int x = fri[group][j]; if (vis[x]) continue; if (data[x].come <= time) { vis[x] = true; ans += time - data[x].come; time += data[x].cost; q.push(x); } } } while (!q.empty()) { int x = q.front(); q.pop(); cout << data[x].name << endl; } printf("%.1lf\n", ans / (1.0 * n));}

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

标签：程序 计算 模拟
上一篇:PTA 7-3 银行业务队列简单模拟
下一篇:PTA 7-6 银行排队问题之单队列多窗口加VIP服务
相关文章

 发表评论

暂时没有评论，来抢沙发吧~