学进去

某工厂生产的产品包含n个（编号为0~n-1）组件，其组装可由多名工人共同协助完成。组装时每个组件都不可遗漏并能按序完成，有些组件存在前置组件（以下简称“前置”），即安装有先后顺序。例如，某产品有6个组件，如下图a所示，组件3的前置是组件1和组件2，即安装组件3需要在组件1和组件2完成之后。若0~5号组件的组装所需单位时间分别为2，5，2，4，3，5，则在工人数量不限的情况下，所有组件安装完成最短需要14个单位时间。

图a

为了梳理产品组件的组装顺序，并计算所有组件安装完成所需的最短时间，编写程序模拟组装过程：先同时组装前置总数为0的组件，完成后更新每个组件的前置总数，再重复以上步骤，直至所有组件安装完毕，程序运行结果如下图b所示，请回答下列问题:

图b

（1）图a所示产品的1号组件组装时长若缩短为3个单位时间，其它时间保持不变，则所有组件安装完成所需最短时间为____个单位时间。
（2）定义如下cal（a, n）函数，参数a列表的每个元素包含两项，a[i][1]是组件编号，a[i][0]是a[i][1]的前置编号，例如a中某个元素值为[2,3]，表示组件2是组件3的前置。该函数的返回值是列表s和列表pre，其中s记录所有组件的相互关系，pre[i]记录初始情况下组件i的前置总数。
def cal（a, n）:

pre=[0]*n

s=[[0 for i in range（n）] for j in range（n）] #创建n×n的二维数组s,元素初始值为0

for i in range（len（a））:

x, y=a[i][0], a[i][1]

s[x][y]=1

pre[y]=____

return pre, s

（3）定义如下proc（n, s, pre）函数，该函数的返回值是列表v， v[i]代表从开始到组件i完成组装所需的最短时间。请在划线处填入合适的代码。
def proc（n, s, pre）:

head=tail=0

que=[0]*n

for i in range（n）:

if pre[i]==0:

que[tail]=i

tail+=1

while :

x=que[head]

head+=1

for i in range（n）:

if s[x][i]==1:

pre[i]-=1

if pre[i]==0:

que[tail]=i

tail+=1

v[i]=max（v[i], ①____）

return v

"""
组装编号0~n-1的单个组件所需时间存入t列表，组件前置关系存入a列表，如图a所需时间t=[2, 5, 2, 4, 3, 5]；a=[[0, 2], [2, 3], [1, 3], [3, 5], [3, 4]]
"""
n=len（t）
print（’编号为0~’+str（n-1）+’的组件组装所需单位时间分别为：’, t）
v=t[:]
pre, s=cal（a, n）
v=proc（n, s, pre）
data=[0]*n
result=[i for i in range（n）] #创建列表result=[0,1,2,……,n-1]
for i in range（n）:

data[i]=v[i]-t[i] #data[i]表示组件i开始安装时间

for i in range（n-1）: #按组件开始安装时间升序排序，开始安装时间相同时按组件序号升序

for j in range（n-1-i）:

if data[result[j]]>data[result[j+1]]:

②____

print（’组件组装顺序:’, result, ’,安装完成所需最短时间:’, max（v））
（4）以下选项与题（3）加框处代码功能相同的是____（多选，填字母）
A．head!=tail          B．head < n          C．tail <= n          D．len（que）>0