问题 F: 进阶实验 3-3.2:银行排队问题之单窗口“夹塞”版

内存限制:128 MB 时间限制:0.000 S
评测方式:文本比较 命题人:
提交:9 解决:8

题目描述

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

输入

输入的第一行是两个整数:1N10000,为顾客总数;0M100,为彼此不相交的朋友圈子个数。若非0,则此后行,每行先给出正整数2L100,代表该圈子里朋友的总数,随后给出该朋友圈里的L位朋友的名字。名字由3个大写英文字母组成,名字间用1个空格分隔。最后行给出位顾客的姓名、到达时间和事务处理时间P(以分钟为单位),之间用1个空格分隔。简单起见,这里假设顾客信息是按照到达时间先后顺序给出的(有并列时间的按照给出顺序排队),并且假设每个事务最多占用窗口服务60分钟(如果超过则按60分钟计算)。

输出

按顾客接受服务的顺序输出顾客名字,每个名字占1行。最后一行输出所有顾客的平均等待时间,保留到小数点后1位。

样例输入 复制

6 2
3 ANN BOB JOE
2 JIM ZOE
JIM 0 20
BOB 0 15
ANN 0 30
AMY 0 2
ZOE 1 61
JOE 3 10

样例输出 复制

JIM
ZOE
BOB
ANN
JOE
AMY
75.2

来源/分类