外卖配送。在一条笔直的大街上,某骑手接了若干个外卖单(均已准备就绪)。骑手配送原则如下:
(1)若当前没有配送任务,优先配送离当前位置最近距离的单子
(2)若在配送中,则当前配送线路不可更改,但可以接沿途的新单,或送达沿途目的地的其他已接单子。
(3)当前单子配送完成后,优先配送手中最早接下的外卖单。
例如有下列单子,骑手初始坐标为2。
外卖单 | A | B | C | D |
起始坐标 | 1 | 4 | 15 | 25 |
终点坐标 | 20 | 16 | 10 | 10 |
配送过程为:先配送A,线路1->20,途中取到B、C,并顺路完成配送B;A完成后配送C,C完成后取送D。
根据上述算法编写了 python 程序,配送完全部单子,回答下列问题:
(1)按图所示的数据,若骑手初始坐标为2,则把D单子送达时骑手共经过多少路程
____?
(2)骑手身上没有外卖时,寻找距离最近单子的函数如下:
def find(a,pos):#列表a存储外卖配送单,pos为当前坐标
k=-1
for i in range(len(a)):
if flag[i]=False:#该单子未派送
if
____:
k=i
return k
划线处应该填入的代码是:
A.k==-1 or abs(a[k][1]-pos)> abs(a[i][1]-pos)
B.k==-1 and abs(a[k][1]-pos)> abs(a[i][1]-pos)
C.k==-1 or a[k][1]-pos> a[i][1]-pos
D.k==-1 or 2*pos> abs(a[i][1]-a[k][1])
(3)请在划线处填入合适的代码,使程序完整。
#生成配送单,存在列表a。a[i]包含4项,a[i][0]为单号、a[i][1]为起始坐标、a[i][2]为终点坐标、a[i][3]初值为-1,代码略
flag=[False]*len(a)
pos=i=0
head=p=-1
while i<len(a)or head!=-1:#处理外卖单
if head==-1:#当前手中没有外卖单子
t=find(a,pos)
if t!=-1:#找到符合条件的单子,处理后开始配送
①
____ p=head
flag[t]=True
pos=a[t] [1]
print(a[t] [0],"单开始配送")
else:
for j in range(len(a)):#寻找可顺路带上加入配送的单子
if flag[j]=False:
st= a[head] [1];ed= a[head] [2]
if min(st,ed)<=a[j][1]<=max(st,ed):#中途加入配送
a[p][3]=j
flag[j]=True
p=a[p] [3]
pre=head;p=a[head] [3]
while p!=-1:#寻找当前身上是否有顺路可送达的单子
t1=②
____#检验该单子是否与当前路径同方向
pos2= a[head] [2]
if t1>0 and min(pos,pos2)<=a[p][2]<=max(pos,pos2):
a[pre] [3]=a[a[pre] [3]][3] #送达后在链表中删除
i+=1
print(a[p] [0],"单子顺带完成")
③
____ else:
pre=p
p=a[p] [3]
i+=1
print(a[head] [0],"单子完成配送,共完成",i,"单")
pos=a[head] [2]
head=a[head] [3]
p=pre