推理流水线总耗时与瓶颈（AI041）- 算法机考高频题型 · 流水线调度 / 数学题解 | AlgoMooc

AI041. 推理流水线总耗时与瓶颈

中等

通过率 100% · 提交 2 · 通过 2

流水线调度数学

这道 OJ 的配套动画

流水线总耗时与瓶颈 · 对应本题的思路、过程和代码

本题改编自算法机考高频题型 · 考点：流水线调度 / 数学 · 难度：中等

模型推理流水线有 p 个阶段（stage，编号 1～p），第 i 个阶段处理一个微批次（micro-batch，即一小批数据）耗时 t[i]。m 个微批次按编号顺序进入流水线：每个阶段同一时刻只能处理一个微批次；微批次 j 完成阶段 i 后立刻可以进入阶段 i+1（阶段之间的缓冲区容量不限）；阶段 i 空闲且微批次 j 已完成阶段 i-1 时，阶段 i 立刻开始处理微批次 j。总完成时间定义为最后一个微批次离开阶段 p 的时刻（从 0 计）。瓶颈阶段定义为耗时最大的阶段，并列时取编号最小者。随后给出一次优化：把阶段 s 的耗时减少 x（保证减少后仍 >= 1；x 可以为 0，表示不做优化）。请输出优化前与优化后的总完成时间和瓶颈阶段。

这类题属于算法机考高频题型中「流水线调度 / 数学」方向的高频题型，通常考察对「流水线调度 / 数学」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。

输入描述

第一行两个整数 p m。第二行 p 个整数 t[1..p]。第三行两个整数 s x。

输出描述

两行，每行两个整数「总完成时间瓶颈阶段编号」：第一行为优化前，第二行为优化后。

数据范围

1 <= p <= 100000；1 <= m <= 10^9；1 <= t[i] <= 10^6；1 <= s <= p；0 <= x <= t[s]-1。答案可达约 10^15，必须使用 64 位整数。

示例

示例 1

输入示例

3 3
2 5 1
2 2

输出示例

18 2
12 2

说明：

常规流水线

示例 2

输入示例

1 10
7
1 3

输出示例

70 1
40 1

说明：

p=1 时退化为串行处理

时间限制 2000 ms · 内存限制 256 MB

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

问小欧 · 图解算法年卡¥99 开通 →

题库上一题下一题

未登录也能直接「运行」调试;「提交」判题需微信登录,你写的代码会自动保留、登录后回到本题继续。

字号13Ctrl+/ 注释 · Ctrl+↵ 提交

1
2

# 在此编写你的代码

写完代码点「提交」，将对全部测试用例判题。

解题思路

首个微批次依次通过全部阶段，需要 sum(t)；流水线填满后，每新增一个微批次都受最慢阶段节拍限制，需要 max(t)。所以总时间为 sum(t)+(m-1)max(t)。优化后重新扫描全部阶段确定总和、最大值和最小编号瓶颈。

正确性说明

首批完成前必须经过每个阶段，填充时间恰为阶段和。稳定运行时任何相邻批次的完成间隔不可能小于瓶颈耗时；其他阶段不慢于瓶颈，又能在无限缓冲下配合该节拍，因此这个下界可达到。两部分相加即总时间。

复杂度分析

每次评估线性扫描 p 个阶段，时间 O(p)，保存耗时数组为 O(p)。

边界与易错点

m=1 时没有后续节拍项；p=1 时退化为串行。乘法使用 64 位，最大值并列时保留第一次出现的编号。

参考代码

import sys


def solve() -> None:
    data = sys.stdin.read().split()
    if not data:
        return
    it = iter(data)
    p = int(next(it)); m = int(next(it))
    t = [int(next(it)) for _ in range(p)]
    s = int(next(it)); x = int(next(it))

    def calc(arr):
        total = sum(arr)
        mx = max(arr)
        bi = arr.index(mx) + 1  # 并列取编号最小
        return total + (m - 1) * mx, bi

    f1, b1 = calc(t)
    t[s - 1] -= x
    f2, b2 = calc(t)
    sys.stdout.write(f"{f1} {b1}\n{f2} {b2}\n")


solve()