第 15 题
答案与解析
第(1)小题
08:27
各城区分别拼车，等待时限从该车第一位乘客的请求上车时刻开始计算。4号改为08:16上车后，城区0的安排如下：
| 时刻 | 事件 | 城区0队列（队首→队尾） |
|---|---|---|
| 08:10 | 1号上车，最迟08:15发车 | 1 |
| 08:11 | 2、3号上车，尚未满4人 | 1、2、3 |
| 08:15 | 1号已等待5分钟，1、2、3号发车 | 空 |
| 08:16 | 4号上车，新车最迟08:21发车 | 4 |
| 08:18 | 7号上车，尚未满载 | 4、7 |
| 08:21 | 4号已等待5分钟，4、7号发车 | 空 |
| 08:22 | 8号上车，开始新车的等待 | 8 |
| 08:27 | 没有后续乘客使车辆提前满载，8号等满5分钟后发车 | 空 |
5、6号前往城区1，不与8号拼车。因此8号的发车时间为08:27。
第(2)①小题
7
程序分析
def sort(data):
i = 0
n = len(data)
flag = True
while i < n - 1 and flag:
flag = False
k = i
for j in range(n-1,i,-1):
if data[j][1] < data[j-1][1]: #A处
data[j],data[j-1] = data[j-1],data[j]
flag = True
k = j
i = k调用sort(data)后，i从0开始，表示本趟参与排序部分的左端位置。j依次取n－1至i＋1，比较j与j－1处的记录；后者的时间较大时交换两条完整记录，使乘客编号、时间、城区的对应关系保持不变。
每趟开始把flag设为False，只有发生交换才改为True，因此整趟没有交换就能在下一次外层条件判断时结束。k先取i，每次交换再更新为j；由于j递减，最终k保存本趟最后一次交换的位置。其左侧无需再比较，执行i = k后，下一趟只检查j＞k的相邻位置。k = i也保证了本趟无交换时，末尾的i = k仍有已定义的值可用。
解题思路
sort(data)反复比较相邻记录，并在后一个上车时间较小时交换，采用冒泡排序。内层从右向左扫描，较小的时间逐步向左移动；程序还用flag判断能否提前结束，并用最后一次交换的位置缩小下一趟的比较范围。
A处是每次相邻元素比较时执行的if判断，条件不成立也计1次。只列出各记录的请求上车时间，按每趟实际边界统计：
| 趟次 | 本趟i | j的取值 | 本趟结束后的时间序列 | 下一趟i | A处次数 |
|---|---|---|---|---|---|
| 1 | 0 | 4、3、2、1 | 550、560、580、570、590 | 2 | 4 |
| 2 | 2 | 4、3 | 550、560、570、580、590 | 3 | 2 |
| 3 | 3 | 4 | 550、560、570、580、590 | 3 | 1 |
第1趟最后一次交换发生在j＝2，第2趟发生在j＝3；第3趟没有交换，flag保持False，循环结束。因此A处共执行4＋2＋1＝7次。
第(2)②小题
A
共用程序分析见第(2)①小题。
给定上车时间依次为490、491、491、496、496、497、498、502，已经非递减。第1趟所有相邻比较均不满足严格小于条件，相等时也不会交换，因此交换分支内的k = j一次都不执行。
删除k = i后，执行到本趟末尾的i = k时，局部变量k尚未赋值，会引发UnboundLocalError。虽然flag已为False，但只有回到下一次while条件判断时才会检查它，不能跳过当前趟末尾的i = k。因此删除该句有影响。
第(3)小题
head = que[k][0]
pa = que[k][head:tail]
ct += 1
程序分析
sort(data)
ct = 0
i = 0
n = len(data)
que = [[1] for i in range(m)]
flag = False
while i < n or flag == True:
...先调用sort(data)，按请求上车时间排列记录。ct从0开始，i从第0条请求开始；que为每个城区建立一个初值为[1]的列表。外层循环将尚有请求未处理与flag记录的本轮处理状态结合起来，控制整个模拟过程。
while i < n and data[i][1] <= ct:
k = data[i][2]
que[k].append(i)
i += 1每次把请求时间不晚于ct的记录加入对应城区的列表，并令i移向下一条请求。由这一条件可知，ct表示当前模拟时刻，i指向尚未加入城区队列的下一条记录。入队保存的是排序后data的下标，不是乘客编号；每个城区列表从下标1开始依次追加这些下标，保持请求时间的先后顺序。先接收ct时刻到达的乘客，再判断发车，所以恰好在等待时限到达的乘客也能参与本时刻拼车。
k = 0
flag = False
while k < m:
①
tail = len(que[k])
if head != tail:
idx = que[k][head]
if ct - data[idx][1] >= t or tail - head >= w:
if head + w < tail:
tail = head + w
②
pa = [data[idx][0] for idx in pa] #将乘客索引转化为乘客编号
print('发车时刻：',ct,'乘客：',pa)
que[k][0] = tail
k -= 1
flag = True
k += 1逐个检查城区时，head指向当前第一条尚未发车的记录，tail初值为列表长度，有效乘客记录位于左闭右开的区间[head, tail)，所以head＝tail表示队列为空。非空时，通过que[k][head]取到队首乘客在data中的下标idx。
队首乘客等待时间达到t，或等待人数tail－head达到w，任一条件成立就发车。如果等待人数超过一车容量，则把本次结束位置tail收缩为head＋w；否则保留原tail。空②需要取出这一车的乘客索引，随后列表推导式将索引转换为实际乘客编号并输出。发车后把本车的结束位置tail写入que[k][0]，保留下一次继续处理的位置；已发车的旧元素仍在列表中，但不再属于有效队列。
发车后执行k -= 1，循环体末尾再执行k += 1，两者抵消，使同一城区能在同一时刻再次接受检查，必要时连续发出多辆车。没有发车时则转向下一个城区。本轮扫描只要遇到非空队列，flag就置为True；即使本轮已将车辆全部发出，flag仍可能为True，因此程序可能再进行一轮空队列检查。
if flag == False and i < n:
ct = data[i][1]
else:
③如果本轮没有遇到非空队列且仍有未到达的请求，就把时间直接跳到下一条请求的上车时刻，避免逐分钟空等。其余情况进入else分支，由空③推进当前时刻，继续接收请求或检查等待时限。
填空分析
①
每个城区列表的第0项初始为1，乘客索引从下标1开始存放；发车后，已有语句que[k][0] = tail把下一段有效数据的起点保存到第0项。因此第0项承担队首位置的保存作用，每次检查该城区时应读出：
head = que[k][0]空队列初始为[1]，此时head＝1且len(que[k])＝1，正好满足head＝tail。
②
进入此处时，head是本车第一位乘客所在的位置，tail已按最多w人的限制确定，指向本车最后一位乘客之后的位置。后续列表推导式要求pa中的元素是data下标，所以直接取城区队列的切片：
pa = que[k][head:tail]Python切片不包含右端点，恰好取出tail－head位乘客，且不会把第0项保存的队首位置混入乘客索引。
③
仍需检查等待时限时，时间要按分钟向前推进。若不推进，ct与各乘客请求时间的差值不会改变；若直接跳到下一条请求，又可能越过已有乘客的最迟发车时刻。填写：
ct += 1下一轮先接收该分钟到达的乘客，再判断是否满载或等待达到t分钟，从而保持题设的发车时序。
问题反馈
解析有疑问或显示异常？请先复制题目信息，再打开反馈表单填写。
题目编号：2026_03_G3_mingxiaoxiezuoti_q015