第 12 题
答案与解析
本题解析
B
程序分析
n = len(a)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + a[i]prefix初始全为0，每次在前一个累计和上加a[i]，因此prefix[t]表示a中前t个元素的和。下标left至k-1这一连续片段的和为prefix[k]-prefix[left]，长度为k-left。
p = [-1] * (n + 1)
head = 0; tail = 0
minlen = n + 1; beststart = -1
for k in range(n + 1):
...p初始全为-1，head、tail都为0，此时head<tail不成立。minlen初值n+1大于任何非空连续片段的长度，beststart初值-1表示尚未找到结果。外层循环按k从0到n依次考察各个前缀位置。
while head < tail and prefix[k] - prefix[p[head]] >= s:
left = p[head]
head = head + 1
if k - left < minlen:
minlen = k - left
beststart = left由prefix[p[head]]可知，p中的元素用于保存prefix的下标，p[head]是当前考察的左端位置。若从该位置到k-1的片段和不小于s，就取出left，并将head增加1，移除这个候选位置。
只有k-left严格小于minlen时，才同时更新最短长度和起始下标；长度相同不会覆盖已有结果。该left已在当前右端形成合格片段，继续保留到更大的k只会使片段更长，所以可以移除并继续检查下一个候选。
while head < tail and prefix[k] <= prefix[p[tail - 1]]:
tail = tail - 1
p[tail] = k
tail = tail + 1若当前prefix[k]不大于末尾候选的前缀和，就令tail减1，删除末尾候选。对于将来的右端，较晚的k既能形成更短的片段，又因前缀和更小或相等而使片段和更大或相等，因此原末尾候选不会更优。
删除完成后将k写入p[tail]，再将tail增加1。结合前面的head增加操作，p[head:tail]构成可从两端移除元素的候选队列，head指向队首，tail指向队尾后一位置；其中保存的下标递增，对应前缀和也严格递增。
整体功能
程序求和不小于s的最短非空连续片段，minlen记录长度，beststart记录其起始下标。相同最短长度再次出现时，保留先找到的片段。
minlen=2、beststart=5对应片段a[5:7]=[95,24]，其和为119，所以必须有s≤119。
在它之前，所有长度为2的片段和依次为47、25、102、30、85。若s≤102，片段[62,40]已能在更早的右端形成长度为2的结果；后续同长度的[95,24]不会覆盖它。若还存在长度为1的合格片段，最终minlen更不可能为2。因此必须有s>102。
反过来，当102<s≤119时，单个元素最大为95，不能形成长度为1的合格片段；前面所有长度为2的片段也都不合格，只有[95,24]符合要求，因此最终得到minlen=2、beststart=5。四个选项中只有115落在这个范围内。
问题反馈
解析有疑问或显示异常？请先复制题目信息，再打开反馈表单填写。
题目编号：2026_04_G3_tianyuxiezuoti_q012