第 15 题

def move(lst, idx):
    if 0 <= idx < len(lst) - 1:
        q = lst[idx]
        k = idx
        while k < len(lst) - 1 and lst[k + 1][1] >= q[1]:
            lst[k] = lst[k + 1]
            k += 1
        lst[k] = q

题干说明 lst 的每个元素保存工作组编号和技能需求总数，因此记录中下标 1 的数据是比较依据。只有 idx 在 0～len(lst)−2 内时才进行处理。q = lst[idx] 暂存当前整条记录，k 从 idx 开始。

当右侧仍有记录，且右侧记录的需求总数不小于 q 时，lst[k] = lst[k + 1] 将右侧记录左移一位，k += 1 使待填位置随之右移。遇到需求总数小于 q 的记录，或待填位置到达列表末尾时，循环结束，再用 lst[k] = q 将暂存的记录放入该位置。

这正是插入排序中的一次插入操作：若 idx 右侧已经按需求总数降序排列，就把 idx 处的记录插入右侧有序部分，使从 idx 开始的部分仍保持降序。与常见的向左寻找插入位置相反，本题向右寻找，将需求总数不小于 q 的记录依次左移。

加框处需要给出本轮待插入记录的下标，使 fsort() 利用 move() 完成整个列表的降序排序。每次插入都要求待插入记录的右侧已经有序，因此先把最右侧下标 n−1 的单条记录作为有序部分，再依次插入下标 n−2、n−3、…、0 处的记录，使有序部分逐步向左扩展。

for i in range(n - 1) 使 i 依次取 0、1、…、n−2。要得到上述待插入下标，应填写：

n - i - 2

原式 n−i 产生的是 n、n−1、…、2，开头两次不满足 move() 的下标条件 0 <= idx < len(lst) - 1，后续又漏掉了下标 1 和 0 处的插入，因而不能保证完成排序。

sel = proc(reqs, cands)

主程序把 reqs 和 cands 传入 proc。按题干注释，reqs[i][j] 表示 i 号工作组对 j 号技能的需求数，cands[i] 则保存 i 号候选人具有的技能编号。函数需要依据这两类数据，为工作组选取合适的候选人。

def proc(reqs, cands):
    """
    根据reqs列表计算生成rsum列表，rsum[i][0]为工作组编号，
    rsum[i][1]为工作组技能需求总数；
    将rsum按工作组技能需求总数降序排序。代码略
    """
    sel = [-1] * len(cands)
    # sel[i]为-1时表示i号候选人未被录用
    while len(rsum) > 0:
        ...
    return sel

函数先生成 rsum，每条记录包含工作组编号及其技能需求总数，并按需求总数降序排列。sel 中每个位置对应一名候选人，初值 −1 表示尚未被录用。

外层循环以 len(rsum) > 0 为条件，说明 rsum 保存尚未结束招募的工作组；每轮处理其中一个工作组，全部工作组结束招募后返回录用结果 sel。

空①需要在每轮扫描候选人之前，将本轮的选择设为“尚未找到合适候选人”。后面的 if bestc == -1 用 −1 判断这一情况，而扫描中只有找到匹配项数大于 0 的候选人才会更新 bestc，因此填写：

bestc = -1

这条初始化必须每轮执行，避免本轮无人合适时仍沿用上一轮的候选人编号。

空②需要让 j 逐一取到当前 i 号候选人具备的技能编号，再用 reqs[num][j] != 0 判断这些技能是否仍被需要。题干中保存该候选人技能编号的列表是 cands[i]，因此填写：

cands[i]

只遍历此人具备的技能，才能使 cnt 正确表示他能满足的技能项数。

空③需要更新当前工作组的技能需求总数，为随后的完成判断和重新插入提供依据。当前工作组编号为 num，需求数保存在 reqs[num]，而 rsum 的首条记录对应这一工作组，因此填写：

rsum[0][1] = sum(reqs[num])

空③在 for 内、与 if reqs[num][i] != 0 同级，每检查一项技能都会执行。重新求和可以兼顾两种情况：需求减少时总数随之减少，需求原本为 0 时总数不变；不能在这里无条件将总数减 1。