器件检测

题目描述:

有 2 组器件共 n 个，要用一台检测设备检测。每个送检器件的信息包含送达时间、检测时长和优先级。优先级有 m(1<m<6)个等级，由高到低分别用 0~m-1 的整数表示。每个机器件的送达时间各不相同。已送达的器件按照各优先级通道分别排队，先到达先入队。设备每次检测都从当前各非空队列中，选取优先级最高的队列的队首器件出队进行检测。（同一时刻出现入队和出队时，先处理入队。）

编写程序模拟检测过程，先合并 2 组器件的数据，然后计算所有器件的平均等待时长，其中每个器件等待时长为其开始检测的时间与送达时间的时间差。（时间单位均为秒）

请回答下列问题：

（1）由题意可知，第 15 题图中器件 A、B、C、D 的检测顺序为 A-C-D-B，A、C、D 的等待时长分别为0、1、0，B 的等待时长是___6____。

输入格式:

第一行n1，接下来 n1 行表示 n1 个器件的信息。

第n1+2行，一个整数 n2, 接下来 n2 行表示 n2 个器件的信息。

输出格式:

一行，表示平均等待时长，保留3位小数。

样例输入:

4
1 5 1
1 7 0
5 5 2
8 3 2
4
1 3 1
6 3 1
7 2 2
10 2 0

样例输出:

average time: 11.375

下载附加文件

提示:

题解：请下载附件。

请完善以下程序：

def merge( lst1, lst2 ):
    i = len( lst1 ) - 1
    j = len( lst2 ) - 1
    for t in range( len(lst2) ):
        lst1.append( [0, 0, 0] ) # 为 lst1 追加一个元素[0, 0, 0]
    k = len( lst1 ) - 1
    while j >= 0:
        if ________________________: #填空1
            lst1[k] = lst1[i]
            i -= 1
        else:
            lst1[k] = lst2[j]
            j -= 1
        k -= 1
    return lst1

def proc( data, m ):
    n = len( data )
    queinfo = []  
    #queinfo用于存储各链表的首节点和尾节点号,有m个元素，每个元素有2项值
    for i in range(m):
        queinfo.append([-1, -1])    
    for i in range(n):
        data[i].append(-1)  # data[i]追加一项-1，变data为多链表而准备：
    #data[x][3]=i表示i号器件和x号器件相同优先级，i号在x号之后送达
    #若data[x][3]=-1,表示x号器件是该优先级队列中的最后一个器件。
    curtime = 0
    waitnum = 0
    i = 0
    ______________ #填空2，送分空
    while i < n or waitnum > 0:      #还有器件未检查
        if i < n and data[i][0] <= curtime:  
        #i号器件在当前时间及之前到达，需到同优先级的队伍中排队等待
            k = data[i][2]    #该器件的优先级k
            if queinfo[k][0] == -1: #若优先级k的队列为空
                queinfo[k][0] = i   #记录该优先级k的队列首节点为i
            else:
                ___________________   #填空3  读取该优先级k的队列的尾节点号给p
                data[p][3] = i   #将i号节点成为p节点的后继
            queinfo[k][1] = i    #更新该优先级k的队列尾节点为i
            waitnum += 1    #等待器件数量+1
            i += 1          
        elif waitnum > 0: 
        #情况1：i<n and data[i][0]>curtime and waitnum>0,
        #i号器件送达时间晚于当前时间，且前面还有器件等待检查
        #情况2：i=n  and waitnum>0,已无器件送来，但前面还有未检查的器件
        #从等待的队列中，找优先级最高的队列里第一个产品送检，
            k = 0
            while queinfo[k][0] == -1:  #找有器件的优先级最高的队列号k
                k += 1
            p = queinfo[k][0]     #读取该队列的首节点号（第一个器件号）给p
            total += curtime - data[p][0]  #计算p器件等待的时间
            curtime += data[p][1]          #计算p器件检查完到达的时间点
        #将p器件出队，由于是链式队列，所以要更新链表首节点的位置，更新为p的后继节点号
            ______________________   #填空4   
            waitnum -= 1  #等待检查的器件数-1
        else:    #i器件送达时晚于curtime，前面又无器件等待检查
                 #隐含的条件是i<n and data[i][0]>curtime and waitnum=0
            curtime = data[i][0]
    return total / n

#data1 = [ [1,5,1], [1,7,0], [5,5,2], [8,3,2] ]
#data2 = [ [1,3,1], [6,3,1], [7,2,2], [10,2,0] ]
data1 = [ ]
data2 = [ ]
n1 = int( input () )
for i in range( n1 ):   #送达时间、检测时长和优先级
    x = list( map( int, input().split() ) )
    data1.append( x)
n2 = int( input () )
for i in range( n2 ):   #送达时间、检测时长和优先级
    x = list( map( int, input().split() ) )
    data2.append( x)
m = 3
data = merge( data1, data2 )
print( "average time: %0.3f" % proc(data, m) )

时间限制: 1000ms
空间限制: 256MB

---

来源: 2023.1 选考真题