5508: 进阶实验 3-3.2:银行排队问题之单窗口“夹塞”版
内存限制:128 MB
时间限制:0.000 S
评测方式:文本比较
命题人:
提交:9
解决:8
题目描述
排队“夹塞”是引起大家强烈不满的行为,但是这种现象时常存在。在银行的单窗口排队问题中,假设银行只有1个窗口提供服务,所有顾客按到达时间排成一条长龙。当窗口空闲时,下一位顾客即去该窗口处理事务。此时如果已知第i 位顾客与排在后面的第j 位顾客是好朋友,并且愿意替朋友办理事务的话,那么第i 顾客的事务处理时间就是自己的事务加朋友的事务所耗时间的总和。在这种情况下,顾客的等待时间就可能被影响。假设所有人到达银行时,若没有空窗口,都会请求排在最前面的朋友帮忙(包括正在窗口接受服务的朋友);当有不止一位朋友请求某位顾客帮忙时,该顾客会根据自己朋友请求的顺序来依次处理事务。试编写程序模拟这种现象,并计算顾客的平均等待时间。
输入
输入的第一行是两个整数:1≤N≤10000,为顾客总数;0≤M≤100,为彼此不相交的朋友圈子个数。若M 非0,则此后M 行,每行先给出正整数2≤L≤100,代表该圈子里朋友的总数,随后给出该朋友圈里的L位朋友的名字。名字由3个大写英文字母组成,名字间用1个空格分隔。最后N 行给出N 位顾客的姓名、到达时间T 和事务处理时间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