大厂真题 / 拼多多

拼多多AI Infra 研发岗 2026-10-11

内容边界：正文完整披露 4 道编程题，以下保留全部题意、约束和正式样例。岗位明确为 AI Infra 研发方向。

本场考试概述

考试时间：2026-10-11

考试岗位：AI Infra 研发岗

难度评级：中等偏难

考点分析：前缀和、滑动窗口与堆、虚拟节点最小生成树、欧拉回路与重构树。

建议策略：先抓住相邻交换只影响一个前缀的性质，再处理窗口最值。后两题都需要先建模：建中心变为虚拟边，巡检补路变为奇度点配对。

第 1 题：冰柜指令看反后仍安全的位置数

题目描述

冰柜容量为 $C$，初始冰量为 $h$，依次执行 $n$ 条整数指令 $a_i$，每条执行后冰量增加 $a_i$。全过程安全指每一步之后的冰量都位于闭区间 $[0,C]$。

必须选一个下标 $1\le i<n$，交换第 $i$ 条与第 $i+1$ 条指令，然后执行完整序列。求使全过程安全的交换下标个数。即使两条指令数值相同，也算一个交换位置；不能把不交换算作一种方案；$n=1$ 时答案为零。

输入格式：仅一组数据。首行 $n,C,h$，其中 $1\le n\le2\times10^5$，$0\le h\le C\le10^9$；第二行 $n$ 个整数，$-10^9\le a_i\le10^9$。前缀和可能超出 32 位有符号整数范围。

输出格式：一个整数，表示合法交换位置数。

样例

输入

5 10 5
4 -8 6 2 -3

输出

2

输入

4 5 2
3 2 -4 1

输出

1

思路分析

第一步：缩小交换的影响范围。 令 $P_0=h$，$P_j=h+\sum_{t=1}^j a_t$。交换后，在第 $i$ 步之前没有变化，第 $i+1$ 步之后累计加入的数也没有变化。唯一变化的是

若对每个交换位置重新模拟，需要 $O(n^2)$；现在只要检查一个新值，并保证其他旧前缀都合法。

第二步：数原本越界的前缀。 设共有 $b$ 个原前缀不在 $[0,C]$ 中。对候选位置 $i$，删去原前缀 $P_i$ 后仍越界的数量为 $b-[P_i\text{ 越界}]$。只有该数量为零且 $P’_i$ 合法时才计数。因此两处以上越界一定无解；唯一越界若在 $P_n$，也无解，因为总和不受交换影响。

第三步：检查边界。 循环仅枚举 $1$ 到 $n-1$，自然覆盖 $n=1$。冰量恰为零或容量都合法。第一组样例可交换的位置为 $i=3,4$；第二组只有 $i=2$。Python 整数自动支持本题所需的大整数。

题解代码

import sys
input = sys.stdin.readline


def count_safe_swaps(n, capacity, initial, a):
    prefix = [initial]
    for value in a:
        prefix.append(prefix[-1] + value)
    bad = sum(not 0 <= value <= capacity for value in prefix[1:])
    answer = 0
    for i in range(1, n):
        remaining_bad = bad - (not 0 <= prefix[i] <= capacity)
        if remaining_bad == 0 and 0 <= prefix[i - 1] + a[i] <= capacity:
            answer += 1
    return answer


def solve():
    n, capacity, initial = map(int, input().split())
    a = list(map(int, input().split()))
    print(count_safe_swaps(n, capacity, initial, a))


solve()

复杂度分析

时间复杂度：$O(n)$，两次线性扫描。

空间复杂度：$O(n)$，保存指令和前缀和。

第 2 题：团子体重可能不变的最长连续日子

题目描述

按日期给出 $n$ 条整数闭区间 $[l_i,r_i]$，代表当天体重的可能值。选择非空连续日子 $[L,R]$，可以忽略至多一天的记录，但忽略后至少保留一天，并且剩下所有区间应包含某个共同整数 $x$。

求所选连续日子的最大长度 $R-L+1$，被忽略的那一天仍计入长度。

输入格式：仅一组数据。首行 $1\le n\le2\times10^5$；随后 $n$ 行各有 $l_i,r_i$，满足 $1\le l_i\le r_i\le10^9$。

输出格式：一个整数，表示最长合法连续段长度。

样例

输入

5
1 5
2 4
8 9
3 6
4 7

输出

5

思路分析

第一步：把交集条件化为最值。 不删除记录时，公共整数存在当且仅当最大左端点不超过最小右端点；由于端点是整数，无须再考虑取整。

设最大左端点来自下标 $i$，最小右端点来自下标 $j$。删除其他任何一天都不会改变这两个冲突的最值，所以只需考虑删除 $i$ 或 $j$。若 $i=j$，该区间被所有其他区间包含，本来就有交集。

第二步：保留两个极值，且不能去重。 当 $i\ne j$ 时，删除 $i$ 后最小右端点不变，只需检查第二大左端点是否不超过最小右端点；删除 $j$ 同理，只需检查最大左端点是否不超过第二小右端点。相同端点来自不同日期时必须分别保存，不能误把第二大理解成第二个不同的数值。

第三步：滑动窗口维护。 合法窗口的任意非空子窗口仍然合法：沿用原来删掉的那一天即可；若子窗口只剩一天，就不删。因此固定右端时，合法左端形成一个后缀，双指针只需单调收缩左端。

代码采用两个懒删除堆：一个存 $(-l_i,i)$，另一个存 $(r_i,i)$。删除堆顶中下标小于左端的旧记录；临时弹出当前最值，清理过期元素后读取第二个极值，再放回。窗口长度至少为二时第二个极值一定存在；长度一直接合法。堆中未到顶的过期元素可暂时保留，总空间仍为 $O(n)$。这种写法牺牲单调队列方案的线性时间，换取更直接的“前两名”维护，仍适用于给定规模。

样例忽略第 3 天后，其余区间都包含整数 $4$，所以答案为 $5$。

题解代码

import sys
import heapq
input = sys.stdin.readline


def top_two(heap, lo):
    while heap[0][1] < lo:
        heapq.heappop(heap)
    first = heapq.heappop(heap)
    while heap and heap[0][1] < lo:
        heapq.heappop(heap)
    second = heap[0][0] if heap else float("inf")
    heapq.heappush(heap, first)
    return first, second


def longest(intervals):
    max_left = []
    min_right = []
    lo = 0
    answer = 0
    for hi, (left, right) in enumerate(intervals):
        heapq.heappush(max_left, (-left, hi))
        heapq.heappush(min_right, (right, hi))
        while lo < hi:
            (negative_left, i), negative_second = top_two(max_left, lo)
            (small_right, j), second_right = top_two(min_right, lo)
            if i == j or -negative_second <= small_right or -negative_left <= second_right:
                break
            lo += 1
        answer = max(answer, hi - lo + 1)
    return answer


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


solve()

复杂度分析

时间复杂度：$O(n\log n)$，每次判定做常数次堆操作，左右端点总移动次数为 $O(n)$。

空间复杂度：$O(n)$，两个堆和区间数组。

第 3 题：冷链物流网络最小总代价

题目描述

有 $N$ 个城市和 $M$ 条已有双向公路。可以花费 $W$ 开通某条公路作为冷链干线，也可以在城市 $i$ 花费 $C_i$ 建物流集散中心。所有建有中心的城市通过航空通道直接互通。求使所有城市连通的最小总代价。

必须至少建一个中心，即使 $N=1$ 也如此。

输入格式：首行 $N,M$，$1\le N\le10^5$，$0\le M\le2\times10^5$；第二行给出 $N$ 个中心费用，$1\le C_i\le10^9$；接下来 $M$ 行各给 $u,v,W$，$1\le u,v\le N$，$u\ne v$，$1\le W\le10^9$，没有重边。

输出格式：一个整数，表示最小总代价。输入结构和样例均为单组数据，没有额外的测试组数。

样例

输入

4 3
50 50 50 10
1 2 10
2 3 10
3 4 100

输出

80

思路分析

第一步：为所有中心引入共同连接点。 新建虚拟城市 $0$，在它与每个城市 $i$ 之间添加权值为 $C_i$ 的边。选这条边就表示在 $i$ 建中心，所有中心经点 $0$ 互通。

第二步：证明等价。 原题任意合法方案都至少有一个中心，将对应虚拟边加入后，$N+1$ 个点连通，费用不变；反过来，扩展图的任何连通方案都包含至少一条与点 $0$ 相连的边，因此能还原出至少一个中心，且所有城市互通。由于边权为正，最优连通方案一定可以删掉环而不增加费用，所以求扩展图的最小生成树即可。

第三步：Kruskal 选边。 将 $N+M$ 条边按费用排序，并查集维护连通块。只有两端分属不同块才选边；采用按大小合并和路径压缩。扩展图共有 $N+1$ 个点，选出 $N$ 条边即可停止。虚拟边保证整个图连通，原公路不连通或没有公路都不影响有解。

样例选择城市 1 和城市 4 的中心，再开通 $1!\leftrightarrow!2$、$2!\leftrightarrow!3$，代价为 $50+10+10+10=80$。单城时直接支付该城中心费用。

题解代码

import sys
input = sys.stdin.readline


def min_total_cost(n, cost, roads):
    edges = [(weight, 0, i + 1) for i, weight in enumerate(cost)]
    edges.extend((weight, u, v) for u, v, weight in roads)
    edges.sort()
    parent = list(range(n + 1))
    size = [1] * (n + 1)

    def find(x):
        while x != parent[x]:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    total = picked = 0
    for weight, u, v in edges:
        u, v = find(u), find(v)
        if u == v:
            continue
        if size[u] < size[v]:
            u, v = v, u
        parent[v] = u
        size[u] += size[v]
        total += weight
        picked += 1
        if picked == n:
            break
    return total


def solve():
    n, m = map(int, input().split())
    cost = list(map(int, input().split()))
    roads = [tuple(map(int, input().split())) for _ in range(m)]
    print(min_total_cost(n, cost, roads))


solve()

复杂度分析

时间复杂度：$O((N+M)\log(N+M))$，排序占主导。

空间复杂度：$O(N+M)$。

第 4 题：环线巡游巡检全部道路的最小花费

题目描述

连通无向图有 $n$ 个景点，编号 $1$ 到 $n$，有 $m$ 条道路，按输入顺序编号 $1$ 到 $m$。道路 $i$ 连接 $u_i,v_i$，过路费为 $w_i$，允许自环和重边。从景点 1 出发，可以反复做两类操作：

• 步行沿一条相邻道路到另一端，支付该边过路费，并巡检这条道路。每条道路至少要这样巡检一次。
• 乘快线到任意不同景点。自选一条连接两点的路线，允许重复经过景点和道路。若该路线上出现的最大道路编号为 $e$，本次票价仅为 $w_e$，并非最大边权，也不是路线边权之和。快线不算步行巡检。

求巡检全部道路、最后回到景点 1 的最小花费。

输入格式：首行 $1\le T\le10^4$。每组先读 $n,m$，$1\le n\le2\times10^5$，$0\le m\le2\times10^5$；随后 $m$ 行按道路编号给出 $u_i,v_i,w_i$，$1\le u_i,v_i\le n$，$1\le w_i\le10^9$。每组图连通，所有组的 $n$ 之和及 $m$ 之和均不超过 $5\times10^5$。

输出格式：每组一行一个最小花费。

样例

输入

1
4 4
1 2 10
2 3 10
3 4 10
1 1 1

输出

32

思路分析

第一步：先支付不可避免的巡检费用。 每条边至少步行一次，基础费用为 $\sum_i w_i$。为了最后回到起点，所有经过的步行边和快线移动组成的连通多重图必须全部为偶度数，也就是存在欧拉回路。原图奇度点必须由额外移动补成偶数，自环贡献两个度数。

额外移动可以分解成连接奇度点的路径与环，正费用环可以省去。一条额外步行路径的费用不小于这条路线上最大编号边的费用，改乘同路线快线不会更贵。快线还满足下面的超度量性质，因此多段快线也可以合成一次而不增加费用。最终只需求奇度点的最小费用两两配对。

第二步：按编号建重构树，不能按边权排序。 从仅含叶子 $1,\ldots,n$ 开始，按道路编号递增加边。如果合并两个不同连通块，就建立一个父节点，两个块的树根为孩子；否则不建节点。每条边的权值记到它加入后所属连通块的树节点上，节点的 $own$ 是挂在这里的所有边权的最小值。自环和成环边虽不合并，却仍然可能显著降低票价，不能丢弃。

对节点 $v$ 定义

根的价格就是自己的 $own$。没有挂边时 $own$ 视为正无穷。

第三步：证明票价公式。 若路线最大编号为 $e$，则在加入前 $e$ 条边的图中，两个端点和边 $e$ 属于同一连通块。反过来，只要在同一块，就能先走到边 $e$、经过它、再到终点；允许绕路和重复使该构造合法。因此所有可能用作最大编号边的候选，正是两点最近公共祖先及其祖先节点上挂的边。于是

沿树向上 $price$ 单调不减，故 $cost(p,q)\le\max(cost(p,r),cost(r,q))$。这也说明合并额外移动不会更贵。

第四步：从下往上配对。 每个叶子若为奇度点，就向上交一个待配点。两个孩子各交一个时，在当前节点配成一对，支付 $price$；否则将剩余的一个向上交。

交换论证：若子树内两点 $p,q$ 分别与外部 $p’,q’$ 配对，把它们改为内部一对、外部一对。内部价格不超过原两对中较小的价格，外部一对由超度量性质不超过原两对中较大的价格，总价不增。因此每个子树最多留一个点向外配是最优的。奇度点总数为偶数，根不会剩点。

父节点编号总大于孩子，因此倒序传播价格、正序合并奇偶即可，无须递归或真正查询 LCA。并查集另用按大小合并，避免重构树很深时影响查询效率。

样例先巡检 1、2、3 号边到达景点 4，花费 30；快线沿 3、2、1、4 号边回到 1，最大编号为 4，票价仅 1；再步行巡检 4 号自环，花费 1，总计 32。$n=1$ 时没有奇度点，答案就是自环费用之和；$m=0$ 的连通图只能是单点，答案为零。

题解代码

import sys
input = sys.stdin.readline


def minimum_tour(n, edges):
    limit = 2 * n + 1
    infinity = 10 ** 30
    parent = [0] * limit
    left = [0] * limit
    right = [0] * limit
    price = [infinity] * limit
    odd = [0] * limit
    dsu = list(range(n + 1))
    size = [1] * (n + 1)
    node_of = list(range(n + 1))

    def find(x):
        while dsu[x] != x:
            dsu[x] = dsu[dsu[x]]
            x = dsu[x]
        return x

    count = n
    total = 0
    for u, v, weight in edges:
        total += weight
        odd[u] ^= 1
        odd[v] ^= 1
        a, b = find(u), find(v)
        if a == b:
            node = node_of[a]
            price[node] = min(price[node], weight)
        else:
            count += 1
            x, y = node_of[a], node_of[b]
            left[count], right[count] = x, y
            parent[x] = parent[y] = count
            price[count] = weight
            if size[a] < size[b]:
                a, b = b, a
            dsu[b] = a
            size[a] += size[b]
            node_of[a] = count
    for node in range(count - 1, 0, -1):
        if parent[node]:
            price[node] = min(price[node], price[parent[node]])
    for node in range(n + 1, count + 1):
        a, b = left[node], right[node]
        if odd[a] and odd[b]:
            total += price[node]
        odd[node] = odd[a] ^ odd[b]
    return total


def solve():
    tests = int(input())
    answers = []
    for _ in range(tests):
        n, m = map(int, input().split())
        edges = [tuple(map(int, input().split())) for _ in range(m)]
        answers.append(str(minimum_tour(n, edges)))
    print("\n".join(answers))


solve()

复杂度分析

时间复杂度：$O((n+m)\alpha(n))$，按编号读入即为处理顺序，树上两遍扫描均为 $O(n)$。

空间复杂度：$O(n+m)$，重构树不超过 $2n-1$ 个节点，另保存输入边。

小结

• 相邻交换后只有一个前缀发生变化，先数原有非法前缀就能线性判定。
• 删一个区间只需考虑两个冲突极值的来源，双指针配合两个最值即可。
• 虚拟节点把建中心费用转成边权，也自动满足至少建一个中心的要求。
• 快线按最大道路编号计价，必须保留自环和成环边的作用；重构树恢复层次后，奇度点可在树上贪心配对。