大厂真题 / 华为

华为 2026-10-23 笔试真题 - 研发岗

本场考试概述

考试时间：2026年10月23日

考试岗位：研发岗

难度评级：中等偏难

考点分析：

第一题：连续分段的最大段和最小化，二分答案与贪心判定（简单）。
第二题：堆、事件驱动模拟、严格抢占与同刻事件顺序（中等）。
第三题：带最低购买量的分组背包，单调队列优化（困难）。

建议策略：

第一题先证明判定函数的单调性，以及“至多 $k$ 段”能够补成“恰好 $k$ 段”。
第二题把同刻事件规则写成明确顺序，不逐单位时间模拟。
第三题不能按效率直接贪心。以总时间为状态，先构造可行上界，再优化区间转移。

第 1 题：分水果

题目描述

有 $n$ 个苹果按固定顺序排列，第 $i$ 个苹果重量为 $nums_i$。要把它们分给 $k$ 个小朋友，要求：

每个小朋友分得一个连续、非空的苹果区间。
所有苹果恰好分完，不能遗漏或重复分配，也不能改变顺序。
尽量减小所有小朋友所得总重量中的最大值。

求这个最大值的最小可能值。这里的目标不是最小化两人重量差，也不是让每段长度相同。

例如重量为 $[4,3,5]$、人数为 $2$ 时，只有两种切法：$[4]$ 与 $[3,5]$ 的最大段和为 $8$；$[4,3]$ 与 $[5]$ 的最大段和为 $7$，因此最优值为 $7$。

输入格式与约束

第一行是 $n,k$，$1\le n\le 1000$，$1\le k\le n$。
第二行是 $n$ 个重量，$1\le nums_i\le 100$。

输出格式

输出一个整数，即恰好分为 $k$ 个连续非空区间时，最大区间和的最小值。

样例 1

输入

5 2
7 2 5 10 8

输出

解释：切成 $[7,2,5]$ 和 $[10,8]$，两段重量分别为 $14$、$18$。若上限只有 $17$，按顺序装入时至少需要三段，因此无法分给两人。

思路分析

第一步：把求最优值改成检查一个上限。

给定最大重量上限 $x$，问题变为：能否把数组切成恰好 $k$ 段，使每段和都不超过 $x$？上限越大，合法切法只会增加，因此可行性具有单调性，可以二分第一个可行的 $x$。

下界取最大单个重量，上界取全部重量之和。

第二步：贪心计算最少需要多少段。

从左到右扫描，当前段还能装下下一个苹果就继续装；否则开启新段。这个策略让当前段尽可能长，从而给后续留下尽可能短的后缀。

第三步：为什么只检查段数不超过 $k$？

如果贪心需要超过 $k$ 段，任何其他方案也无法更少。如果只需少于 $k$ 段，因为 $k\le n$，必定还能从含多个苹果的段中继续切分，直到恰好 $k$ 段。所有重量均为正，拆分不会增大任何一段的重量。

因此判定条件是 segments <= k，不应写成相等。

正确性证明

固定上限 $x$。贪心第一段取能容纳的最长前缀，任何合法方案的第一段都不可能更长。归纳地，贪心用相同段数能够覆盖的前缀不短于其他方案，所以贪心所需段数最少。

由可继续拆分的性质，最少段数不超过 $k$ 当且仅当存在恰好 $k$ 段的合法方案。这个条件随 $x$ 单调，二分保留包含最小可行值的区间，最终返回的值就是所求最优值。

题解代码

import sys
input = sys.stdin.readline


def split_fruits(nums, k):
    lo, hi = max(nums), sum(nums)
    while lo < hi:
        limit = (lo + hi) // 2
        segments, current = 1, 0
        for weight in nums:
            if current + weight > limit:
                segments += 1
                current = weight
            else:
                current += weight
        if segments <= k:
            hi = limit
        else:
            lo = limit + 1
    return lo


def solve():
    n, k = map(int, input().split())
    nums = list(map(int, input().split()))
    print(split_fruits(nums[:n], k))


if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度：$O(n\log(S+1))$，其中 $S=\sum nums_i$；每次二分做一遍线性扫描。

空间复杂度：$O(n)$，用于存放重量数组；判定过程只使用常数个辅助变量。

第 2 题：多租户优先级任务调度模拟

题目描述

单机一次只能执行一个任务。每个任务有唯一编号 id、优先级 $p$、到达时间 $a$ 和所需执行时长 $t$。

调度遵循以下规则：

CPU 空闲时，从已经到达但尚未完成的任务中选择下一个任务。
选择次序为：优先级 $p$ 降序，到达时间 $a$ 升序，输入行顺序升序。编号 id 不参与同级排序。
新任务到达时，只有优先级严格高于当前任务，才会抢占。相同优先级不抢占。
被抢占的任务保存剩余时长并重新进入就绪队列，原来的优先级、到达时间和输入顺序不变。
若当前任务完成与新任务到达发生在同一时刻，先记录当前任务完成，再接收该时刻到达的全部任务，然后进行选择。
时长为 $0$ 的任务被选中执行后立即完成，不消耗时间；它仍遵守就绪排序及抢占规则，不能绕过更高优先级任务直接在到达时完成。

输出所有任务的完成顺序。

输入格式与约束

第一行是任务数量 $N$，$1\le N\le 200000$。
随后 $N$ 行，每行是 id p a t。
编号两两不同，$1\le id\le 2^{31}-1$。
$p$ 为有符号 32 位整数，即 $-2^{31}\le p\le 2^{31}-1$。
$0\le a,t\le 10^9$。
输入不保证按到达时间排序。同一时刻可有多个任务到达。

输出格式

输出一行 $N$ 个任务编号，按完成先后排列，用空格分隔。累计运行时间可能超出 32 位范围，Python 整数可以直接处理。

样例 1

输入

输出

3 4 5 1 2

解释：

时刻 $0$，任务 $1$ 开始运行。
时刻 $2$，任务 $2,3,4$ 到达；任务 $3$ 优先级最高，抢占任务 $1$，后者剩余 $4$ 个时间单位。
时刻 $3$，任务 $3$ 完成，选择任务 $4$。
时刻 $5$，任务 $4$ 完成，同时任务 $5$ 到达。先记录 $4$ 完成，再运行任务 $5$。
时刻 $6$，任务 $5$ 完成；之后依次完成任务 $1$ 和 $2$。

思路分析

第一步：只在状态可能改变时推进时间。

执行时长可以非常大，逐单位模拟不可行。任务集合只会在“新任务到达”和“当前任务完成”时变化。在两个事件之间，当前任务连续执行，不必模拟中间每个时刻。

第二步：分别管理到达顺序和就绪顺序。

到达序列按照 (a, 输入序) 排序，并用指针逐个接收。就绪队列使用最小堆，键为 (-p, a, 输入序)；取负号后，优先级越大的任务越靠前。任务编号、剩余时间放在键后，不影响已经唯一确定的排序。

running 保存正在执行的任务，不在堆里。所有到达时间不晚于当前时间的任务先入堆，再比较堆顶与 running 的优先级。只有严格更高时才把当前任务放回堆。

第三步：完成时刻与到达时刻比较时必须含等号。

设当前时间为 $now$、剩余时长为 $rest$，预计完成时刻为 $end=now+rest$，下次到达时刻为 $next$。

若 $end\le next$，先把当前任务记入完成序列，并令 $now=end$。
若 $end>next$，扣除已经运行的 $next-now$，令 $now=next$，下一轮接收新任务并检查抢占。

当堆和 CPU 都空闲时，直接跳到下个到达时刻。零时长任务在选中后走完成分支，不增加时间；循环仍然会减少未完成任务数，因此不会卡住。

正确性证明

在每轮接收事件后，堆中恰好是已经到达、尚未完成、且不在执行中的任务，键值保持题目要求的原始排序；running 的剩余时长等于总时长减去实际执行时长。

若堆顶优先级不高于当前任务，其余就绪任务也不可能抢占。若更高，放回当前任务并取堆顶恰好执行严格抢占规则。空闲时取堆顶同样符合选取顺序。

下一次状态变化一定是到达或完成，算法选择较早事件；二者同刻时由不等号中的等号保证先完成。每轮都精确模拟下一事件，所以归纳得到的完成序列与规定调度一致。

题解代码

import sys
from heapq import heappush, heappop
input = sys.stdin.readline


def schedule(tasks):
    arrivals = sorted((a, i, task_id, p, duration)
                      for i, (task_id, p, a, duration) in enumerate(tasks))
    n = len(arrivals)
    ready = []
    finished = []
    running = None
    now = 0
    ptr = 0
    while len(finished) < n:
        while ptr < n and arrivals[ptr][0] <= now:
            a, i, task_id, p, duration = arrivals[ptr]
            heappush(ready, (-p, a, i, task_id, duration))
            ptr += 1
        if running is not None and ready and ready[0][0] < running[0]:
            heappush(ready, running)
            running = None
        if running is None:
            if not ready:
                now = arrivals[ptr][0]
                continue
            running = heappop(ready)
        neg_p, a, i, task_id, remaining = running
        end = now + remaining
        if ptr == n or end <= arrivals[ptr][0]:
            now = end
            finished.append(task_id)
            running = None
        else:
            next_time = arrivals[ptr][0]
            remaining -= next_time - now
            now = next_time
            running = (neg_p, a, i, task_id, remaining)
    return finished


def solve():
    n = int(input())
    tasks = [tuple(map(int, input().split())) for _ in range(n)]
    print(*schedule(tasks))


if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度：$O(N\log N)$。到达排序占 $O(N\log N)$；每次抢占都由到达事件引起，抢占总次数至多 $O(N)$，因此堆操作总数为 $O(N)$。

空间复杂度：$O(N)$，存储任务、到达序列、就绪堆及完成序列。

第 3 题：AI Agent 管理大师

题目描述

需要向若干 AI Agent 分配总量至少为 $m$ 的项目任务。共有 $n$ 个 Agent，第 $i$ 个的委托效率为 $w_i$ 单位工作量/分钟。

可以不使用一个 Agent；若使用，则必须购买整数分钟数 $x_i$，满足 $a_i\le x_i\le b_i$。购买 $x_i$ 分钟能够支持 $w_i x_i$ 的工作量。

同一时间只能与一个 Agent 交流，因此总耗时是所有购买分钟数之和，不是最长的单个交互时长。允许购买能力超过实际需求，也不需要考虑 Agent 后续执行项目的时间。

求满足下式的最小总购买时间：

\[\sum_{i=1}^{n} w_i x_i\ge m,\qquad x_i\in\{0\}\cup([a_i,b_i]\cap\mathbb Z).\]

若所有 Agent 都用到最高限额仍无法达到目标，输出 $-1$。

输入格式与约束

第一行是 Agent 数量 $n$ 和工作量 $m$，给定上界为 $n\le 50$、$m<10^9$。
随后 $n$ 行，每行是 $w_i,a_i,b_i$。
$10^3\le w_i<10^4$，$1\le a_i<10^5$，$1\le b_i<10^5$。
如果 $a_i>b_i$，这个 Agent 没有合法的正购买时长，只能不使用。
购买分钟数为整数。实现也处理目标工作量为 $0$ 的边界，答案为 $0$。

输出格式

输出最少购买分钟数；无法完成则输出 $-1$。

样例 1

输入

输出

解释：选择第二个 Agent，购买最低要求的 $4$ 分钟，支持 $20000$ 工作量，已经覆盖目标。虽然第一个 Agent 效率更高，但它至少需要购买 $5$ 分钟，反而不优。

样例 2

输入

输出

-1

解释：全部买满最多支持 $6000\times2+5000\times3+4000\times3=39000$ 工作量，小于目标 $150000$。

思路分析

第一步：最低消费使效率贪心失效。

若没有最低购买量，优先使用高效率 Agent 很自然。但样例 1 已经说明，高效率 Agent 的启动门槛可能比另一个 Agent 的完整方案还贵。

工作量上界很大，不宜以工作量作背包下标；购买时长的范围相对更小，可以维护“恰好花费 $t$ 分钟时能支持的最大工作量”。

第二步：写出分组背包转移。

设 f[t] 是只考虑已处理 Agent、总时间恰为 $t$ 时的最大工作量。不可达状态为 $-1$，初始化 $f[0]=0$。

加入参数为 $(w,a,b)$ 的 Agent 后：

\[g[t]=\max\left(f[t],\max_{a\le x\le b}\{f[t-x]+wx\}\right).\]

第一项是不使用，第二项是购买 $x$ 分钟。每个 Agent 只能处理一层，转移必须读取旧数组 f，不能从已经更新的 g 再次购买同一个 Agent。

第三步：换元形成滑动窗口最大值。

令 $s=t-x$，则合法旧下标范围为 $t-b\le s\le t-a$，转移改写成：

\[g[t]=\max\left(f[t],wt+\max_{t-b\le s\le t-a}\{f[s]-ws\}\right).\]

随着 $t$ 递增，窗口的两端同步右移。用单调队列保存候选下标及其值 $f[s]-ws$：

把新进入窗口的下标 $s=t-a$ 加入队尾；不可达状态不加入。
若队尾值不大于新值，弹出队尾。它值不更好，而且更早过期，以后都不会成为最优候选。
弹出下标小于 $t-b$ 的队头。
队头就是当前窗口的最大值，用它更新 g[t]。

每个下标最多入队、出队一次，单层转移变成线性。

第四步：用可行方案缩小时间容量，但不把贪心当成答案。

直接使用 $\sum b_i$ 作容量虽然正确，但 Python 的常数和内存都较大。先按效率降序遍历 Agent，用下面的方式构造一个可行方案：若还差 $remaining$ 工作量，购买

\[x=\min\left(b,\max\left(a,\left\lceil remaining/w\right\rceil\right)\right)\]

分钟，扣掉相应能力，直到覆盖目标。预先检查总能力足够后，这个过程一定能结束。所得总时间 $U$ 只是一个可行上界，最优值不会大于它，DP 可以忽略所有时间超过 $U$ 的状态。

记有效 Agent 的最小效率为 $w_{\min}$、最大最低购买量为 $a_{\max}$。完成前的 Agent 都买满；最后一个 Agent 最多因为最低购买量多买 $a_{\max}-1$ 分钟，因此：

\[U\le\min\left(\sum b_i,\left\lceil m/w_{\min}\right\rceil+a_{\max}-1\right).\]

DP 过程中一旦找到更短的可行时间，还可以继续收紧上界，因为后续新增购买时长不会为负。扫描按时间递增，当前层第一次达到目标后便可停止向更大时间转移。采用 array('q') 存储 64 位整数，减少大规模 Python 整数列表的内存负担。

正确性证明

对 Agent 数量归纳。初始只有时间 $0$、能力 $0$ 可达，状态定义成立。对于新 Agent，每个合法方案要么不用它，要么唯一对应某个 $x\in[a,b]$ 和旧方案时间 $s=t-x$。转移枚举了所有这些选择并取最大能力，所以 g 满足相同定义。

单调队列只删除过期候选，或删除值不更大且更早过期的候选。被后者替代的状态不可能在任何未来窗口优于新状态，因此队头精确实现转移中的最大值。

容量裁剪只删除比已知可行方案更耗时的状态。后续操作仅增加非负时长，被删除状态不可能产生更短答案；对答案没有影响。最终从小到大寻找工作量至少为 $m$ 的状态，得到的就是最小合法时间。若全部能力不足，则任何方案都不可能达到目标，返回 $-1$ 正确。

题解代码

import sys
from array import array
from collections import deque
input = sys.stdin.readline


def min_time(agents, target):
    if target <= 0:
        return 0
    agents = sorted((row for row in agents if row[1] <= row[2]), reverse=True)
    if sum(w * b for w, a, b in agents) < target:
        return -1

    remaining, upper = target, 0
    for w, a, b in agents:
        take = min(b, max(a, (remaining + w - 1) // w))
        upper += take
        remaining -= w * take
        if remaining <= 0:
            break

    f = array('q', [0])
    for w, a, b in agents:
        if a > upper:
            continue
        old_top = len(f) - 1
        top = min(upper, old_top + b)
        g = f[:top + 1]
        g.extend(array('q', [-1]) * (top + 1 - len(g)))
        candidates = deque()
        for t in range(a, top + 1):
            s = t - a
            if s <= old_top and f[s] >= 0:
                value = f[s] - w * s
                while candidates and candidates[-1][1] <= value:
                    candidates.pop()
                candidates.append((s, value))
            while candidates and candidates[0][0] < t - b:
                candidates.popleft()
            if candidates:
                value = w * t + candidates[0][1]
                if value > g[t]:
                    g[t] = value
            if g[t] >= target:
                upper = t
                break
        f = g[:upper + 1]
    return next(t for t, work in enumerate(f) if work >= target)


def solve():
    n, target = map(int, input().split())
    agents = [tuple(map(int, input().split())) for _ in range(n)]
    print(min_time(agents, target))


if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度：$O(n\log n+nU)$，$U$ 是初始构造的可行时间上界。每层扫描至多 $U+1$ 个状态，每个候选至多入队、出队一次。动态缩小上界会减少实际工作量，但不改变这个最坏界。

空间复杂度：$O(n+U)$。Agent 列表占 $O(n)$，滚动数组和单调队列占 $O(U)$；工作量应使用足够宽的整数，不能用 32 位有符号整数保存所有状态值。

小结

分水果：将优化目标转成单调判定，证明贪心段数最少，以及可补足段数。
优先级调度：把业务规则落实到堆键、抢占条件和同刻事件次序，事件驱动避免时间跨度造成超时。
Agent 分配：最低购买量是离散决策，不能只看单位效率；换元后的窗口最大值把背包转移从区间枚举降为线性。

这篇文章有帮助吗？

| GitHub 留言