大厂真题 / 拼多多

拼多多通用岗 2026-10-25 笔试真题

本场考试概述

考试时间：2026 年 10 月 25 日

考试岗位：通用岗（未区分具体岗位）

难度评级：中等偏难

考点分析：

• 第一题：免费操作的不变量、排序后的目标位置。
• 第二题：大根堆、强制切分与贪心匹配。
• 第三题：区间成本单调性、双指针与单调队列。
• 第四题：离线离散化、区间加与全局最大值。

建议策略：前两题先证明贪心或计数结论，不必模拟完整调度过程。后两题先写出维护对象的数学表达式，再选择数据结构；尤其要区分检查费用与模式切换费用、商品位置与价格窗口。

第 1 题：列车排序的最少耗电量

题目描述

一列火车有 $N$ 节车厢，第 $i$ 节的卸载优先级为 $A_i$，所有优先级互不相同。需要将车厢按优先级从左到右严格递增排列。

允许任意次使用以下两种操作：

1. 反转连续 2 节车厢，消耗 1 单位电。
2. 反转连续 3 节车厢，不消耗电。

每次可以选择任意合法的连续位置，求完成排序所需的最少电量。

输入描述

第一行输入测试组数 $T$。接下来每组输入一个整数 $N$，随后输入 $N$ 个优先级；题目给出的格式中，每组这些数字位于同一行。

约束为 $1\le T\le10$，$1\le N\le10^5$，$0\le A_i\le10^9$，每组的优先级两两不同。

输出描述

每组输出一个整数，表示最少耗电量。

样例

输入

2
4 2 1 3 4
5 10 8 5 3 2

输出

1
0

第一组交换前两节即可。第二组虽然逆序，但每节车厢与其排序后的目标位置具有相同奇偶性，免费操作足够完成调整。

思路分析

第一步：只保留大小关系。

把数组按优先级排序。某元素在排序结果中的下标就是它的目标位置，称为 rank。使用统一的 0 基下标，只需讨论原下标 index 与目标下标的关系。

第二步：识别免费操作能做到什么。

连续三节 $(x,y,z)$ 反转为 $(z,y,x)$，实际上只交换下标 $i$ 与 $i+2$。它不会改变任何元素所在位置的奇偶性。

反过来，所有偶数下标形成一条间隔为 2 的链，奇数下标也形成一条链。三节反转就是各链上的相邻交换，所以同一奇偶类内可以免费实现任意排列。问题只剩下：有多少元素必须从一个奇偶类移动到另一个奇偶类。

第三步：求下界并构造达到下界的方案。

设当前位置与目标位置奇偶性不同的元素有 $m$ 个。付费操作交换相邻两节，至多纠正两个元素，因此至少付费 $m/2$ 次。

偶数位置的数量固定，因此“应去奇数位置却在偶数位置”和“应去偶数位置却在奇数位置”的元素数量必定相同。每次从两类错位元素中各选一个，通过免费操作把它们移到一对相邻位置，再付费交换，恰好修复两个错位。重复后再免费整理各奇偶类内部的顺序。

正确性证明

免费操作保持奇偶类，故每个奇偶错位元素都必须参与付费交换，单次最多修复两个，得到 $m/2$ 的下界。上述配对构造每次正好修复两个，且免费重排不会制造新的奇偶错位，最终恰用 $m/2$ 次付费操作完成排序。上下界相等，因此答案为 $m/2$。

题解代码

import sys

input = sys.stdin.readline


def min_power(priorities):
    order = sorted(range(len(priorities)), key=priorities.__getitem__)
    mismatch = sum((rank - index) % 2 for rank, index in enumerate(order))
    return mismatch // 2


def solve():
    numbers = (int(token) for line in sys.stdin for token in line.split())
    t = next(numbers)
    for _ in range(t):
        n = next(numbers)
        priorities = [next(numbers) for _ in range(n)]
        print(min_power(priorities))


if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度：单组 $O(N\log N)$，排序为主要开销；多组累加各组的排序代价。

空间复杂度：单组 $O(N)$，用于优先级数组、排序下标和排序辅助空间。

易错点

不能用优先级本身的奇偶性判断，应比较元素的原下标与排序后的下标。本题求的是耗电量，不是所有操作的最少次数，不能直接套逆序对计数。

第 2 题：绳子对半切割能否得到指定长度

题目描述

初始只有一根长度为 $L$ 的绳子。每次选择一段长度 $x\ge2$ 的现有绳子，将其切成长度为 $\lfloor x/2\rfloor$ 和 $\lceil x/2\rceil$ 的两段；长度为 1 的绳子不能再切。

可以切割任意次，也可以不切。判断最终能否恰好得到 $n$ 根绳子，其长度多重集为 $a_1,\ldots,a_n$。不允许拼接，也不允许留下多余绳子；目标长度的排列顺序没有要求。

输入描述

第一行输入测试组数 $T$。每组第一行输入 $L,n$，第二行输入 $n$ 个目标长度。

约束为 $1\le T\le50$，$1\le L\le10^{14}$，$1\le n\le10^5$，$1\le a_i\le10^9$。

输出描述

每组输出 YES 或 NO。

样例

输入

3
10 1
10
16 5
8 4 2 1 1
16 4
9 8 7 6

输出

YES
YES
NO

第一组无需切割。第二组依次保留 8、4、2，并把最后的 2 切成两个 1。第三组目标总长不等于初始长度。

思路分析

第一步：检查长度守恒。

切割只改变段数，不改变总长度，所以 $\sum a_i=L$ 是必要条件。它不是充分条件：即使总长相等，规定的对半切割方式也可能无法形成指定长度。

第二步：始终比较最大的现有绳段与最大目标。

将目标长度降序排序，用大根堆保存尚未匹配的绳段，初始只有 $L$。设堆顶长度为 $p$，当前最大目标为 $a_j$：

• $p<a_j$：现有段都太短，继续切只会更短，无解。
• $p>a_j$：这段比全部剩余目标都长，不能直接保留，必须继续对半切。
• $p=a_j$：将这根绳子与目标匹配，二者从待处理集合中移除。

第三步：限制切割数量。

如果当前未匹配绳段数大于未匹配目标数，那么每段至少会留下一个最终片段，不可能再减回去，应立即失败。加入这个显式检查后，段数始终受 $n$ 限制，避免把大长度绳子无意义地细分到单位段。

正确性证明

大于最大目标的绳段不可能直接成为任何目标，切开是强制选择；小于最大目标时，任何现有段及其后代都不可能达到该目标，判无解正确。

相等时，若某个可行方案不是使用当前这段来匹配最大目标，它必然使用另一段等长绳子，因为没有更长段，而短段不能拼接。等长绳段的后续切割能力完全相同，可以交换两段在该方案中的角色，从而得到一个保留当前段的可行方案。因此直接匹配不会排除可行解。

每步操作均保持可行性判断，且总长守恒、目标全部匹配后没有剩余段，故算法输出准确。

题解代码

import heapq
import sys

input = sys.stdin.readline


def can_split(length, targets):
    if sum(targets) != length:
        return False
    targets = sorted(targets, reverse=True)
    heap = [-length]
    matched = 0
    while matched < len(targets):
        if not heap or len(heap) > len(targets) - matched:
            return False
        piece = -heapq.heappop(heap)
        target = targets[matched]
        if piece < target:
            return False
        if piece == target:
            matched += 1
        else:
            half = piece // 2
            heapq.heappush(heap, -half)
            heapq.heappush(heap, -(piece - half))
    return not heap


def solve():
    numbers = (int(token) for line in sys.stdin for token in line.split())
    t = next(numbers)
    for _ in range(t):
        length, n = next(numbers), next(numbers)
        targets = [next(numbers) for _ in range(n)]
        print('YES' if can_split(length, targets) else 'NO')


if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度：单组 $O(n\log n)$。目标排序后，每次匹配移除一个目标，每次切割增加一个绳段；段数限制使切割总次数为 $O(n)$，每次堆操作为 $O(\log n)$。

空间复杂度：单组 $O(n)$，存储目标与待处理绳段堆。

易错点

奇数长度切成向下取整和向上取整两段，不能都使用整除结果。目标长度均为正，因此进入“必须切割”分支时 piece > target >= 1，不会把长度 1 切出长度 0。

第 3 题：有限免检机会下的最长检查批次

题目描述

传送带上按顺序放置 $n$ 件货物。第 $i$ 件的检查时间为 $a_i$，所需模式为 $c_i\in{0,1}$。

选择一段非空连续货物作为一个批次。开始时可以直接使用第一件货物所需模式，不额外收费；批内相邻两件的模式不同时，需要增加 $D$ 的切换时间。

每个批次最多使用一次免检机会：选其中至多 $K$ 件连续货物，将它们的检查时间改为 0。免检货物仍占据原位置，模式以及由此产生的切换时间全部保留。

总耗时不得超过预算 $B$，求最多可以选择多少件连续货物。

输入描述

第一行输入 $n,K,B,D$，第二行输入 $n$ 个检查时间，第三行输入 $n$ 个模式。

约束为：

• $1\le n\le2\times10^5$，$1\le K\le n$。
• $0\le B\le10^{18}$，$0\le D\le10^9$。
• $1\le a_i\le10^9$，$c_i\in{0,1}$。

输出描述

输出满足预算的最长批次长度。

样例 1

输入

6 2 9 2
4 7 2 5 1 6
0 0 1 1 0 0

输出

4

选择前四件，免检前两件后检查时间为 $2+5=7$，模式切换一次增加 2，总耗时为 9。

样例 2

输入

3 2 3 1
8 1 8
0 1 0

输出

2

任意相邻两件可以一起免检，耗时仅为一次模式切换。三件全选时，即便免检两件，仍至少需要检查时间 8 和切换时间 2。

思路分析

第一步：固定批次，求最佳免检收益。

所有 $a_i$ 都为正，免检段越长越不吃亏。批次长度不超过 $K$ 时可以全部免检；超过 $K$ 时，最优方案一定免检其中恰好连续 $K$ 件。

使用 0 基下标。令 prefix[t] 为前 $t$ 件的检查时间总和，switches[i] 为下标 0 到 $i$ 之间的模式切换次数。对批次 $[l,r]$：

当批次较长时，免检收益就是批内长度 $K$ 的最大子段和。预处理

合法免检起点恰为 $l\le s\le r-K+1$。

第二步：证明滑动窗口的单调性。

从任意批次删掉一个端点，将原来的最优免检段与缩短后的批次求交，仍得到长度不超过 $K$ 的连续免检段。保留下来的检查成本不会增加，模式切换次数也不会增加。因此缩短批次不会提高最优成本；等价地，固定左端点向右扩张时，成本不会下降。

于是右端点逐个向右加入。如果当前批次超预算，就持续右移左端点，直到重新可行。已经被移除的左端点，在右端点进一步扩张后也不可能恢复可行，无需回头。

第三步：用单调队列维护免检收益。

队列保存候选起点，按起点递增、对应 $w_s$ 严格递减排列：

• 新右端点形成一个完整长度 $K$ 的段时，把它加入候选集合。
• 入队前弹出所有收益不大于新段的队尾。新段更靠右、过期更晚，旧段永远不可能更优。
• 左端点右移后，弹出起点小于左端点的队头。

队首就是最大免检收益。窗口不足 $K$ 时无需队列查询，直接免检全部检查时间。

正确性证明

单调队列只删除已离开批次的候选，或被收益不小且过期更晚的候选支配的旧段，因此始终保留当前最大免检收益，计算出的成本准确。

固定右端点时，算法从上次左端点开始收缩，所有被丢弃的窗口均已超预算；更早丢弃的左端点又由成本单调性保证仍不可能可行。停止时得到该右端点下的最长可行批次。对全部右端点取最大长度，即为全局最优。

题解代码

from collections import deque
import sys

input = sys.stdin.readline


def longest_batch(times, modes, k, budget, switch_cost):
    n = len(times)
    prefix = [0] * (n + 1)
    switches = [0] * n
    for i, value in enumerate(times):
        prefix[i + 1] = prefix[i] + value
        if i:
            switches[i] = switches[i - 1] + (modes[i] != modes[i - 1])
    window_sum = [prefix[s + k] - prefix[s] for s in range(n - k + 1)]
    candidates = deque()
    left = answer = 0
    for right in range(n):
        start = right - k + 1
        if start >= left:
            while candidates and window_sum[candidates[-1]] <= window_sum[start]:
                candidates.pop()
            candidates.append(start)
        while True:
            while candidates and candidates[0] < left:
                candidates.popleft()
            total = prefix[right + 1] - prefix[left]
            if right - left + 1 <= k:
                saved = total
            else:
                saved = window_sum[candidates[0]]
            cost = total - saved + switch_cost * (switches[right] - switches[left])
            if cost <= budget:
                break
            left += 1
        answer = max(answer, right - left + 1)
    return answer


def solve():
    n, k, budget, switch_cost = map(int, input().split())
    times = list(map(int, input().split()))
    modes = list(map(int, input().split()))
    print(longest_batch(times, modes, k, budget, switch_cost))


if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度：$O(n)$。两个端点各自至多右移 $n$ 次，每个免检起点至多入队和出队各一次。

空间复杂度：$O(n)$，包括前缀数组、定长窗口和与单调队列。

易错点

• 免检不取消模式切换费，不能把免检段从序列中物理删除。
• $B=0$ 不意味着能选满 $K$ 件：相邻模式不同且 $D>0$ 时，即使检查费用为零也可能超预算。
• 单件货物总能全部免检，且没有模式切换，所以题目范围内答案至少为 1，收缩循环一定能停下；不可能输出 0。

第 4 题：动态调价后的最大可选种数

题目描述

水果摊有 $n$ 种橘子，第 $i$ 种价格为 $a_i$。每天将其中一种橘子的价格永久改为新值。每次修改完成后，需要选择尽可能多的不同种类，使所选价格的最大值与最小值之差不超过 $k$。

不同种类可以价格相同，每种仍单独计数。选择不要求在商品编号上连续，只要求价格范围满足条件。

输入描述

第一行输入 $n,k$，第二行输入 $n$ 个初始价格，第三行输入修改次数 $q$。接下来 $q$ 行，每行输入 $p,x$，表示将第 $p$ 种的价格赋值为 $x$。

约束为 $1\le n\le5\times10^4$，$0\le k\le10^8$，$1\le q\le10^5$，$1\le a_i,x\le10^8$，$1\le p\le n$。

输出描述

每次修改后输出一行最多可选种数。初始状态不单独输出。

样例

输入

5 2
1 2 3 10 11
3
4 3
5 2
1 100

输出

4
5
4

三次修改后的价格分别为 [1,2,3,3,11]、[1,2,3,3,2] 和 [100,2,3,3,2]。前两次选价格区间 $[1,3]$ 内的所有种类，最后一次可以选 $[2,4]$ 内的四种。

思路分析

第一步：把选择集合转成价格窗口。

一旦选定价格区间 $[v,v+k]$，区间内所有种类都可以加入，不会破坏最大最小差条件。只需寻找容纳商品最多的窗口。

对于任意非空可行集合，令其中最低价格为 $v$，集合内所有价格都在 $[v,v+k]$ 中。因此至少有一个最优窗口以下界为某个当前价格。注意，这只说明原来选中的商品仍被包含，不是说平移后的窗口包含原窗口的所有坐标。

第二步：提前离散化所有可能价格。

读入初始价格和全部修改值，排序去重得 $v_0<\cdots<v_{m-1}$，其中 $m\le n+q$。为每个候选下界维护

答案为所有 $f_i$ 的最大值。候选下界即使当前没有商品，也只代表一个合法价格窗口，不会让答案虚增；当前所有可能最优下界又都在候选集中。

第三步：商品的一次增删对应区间加。

价格为 $x$ 的一个种类被窗口 $[v_i,v_i+k]$ 包含，当且仅当

这在离散数组上是一段连续下标。设 $x=v_r$，low[r] 为第一个满足 $v_i\ge v_r-k$ 的下标，则该商品恰对闭区间 [low[r], r] 的每个 $f_i$ 贡献 1。

所以一次调价只需删除旧价格的区间贡献，再加入新价格的区间贡献。初始化时可对所有商品做差分，再求前缀和得到全部 $f_i$。

第四步：维护区间加与全局最大值。

线段树节点保存 maximum 和 tag。这里仅查询全局最大值，可以使用“不下传标记”的写法：父节点标记只保存在父节点，子节点最大值不包括祖先标记，并保持

完全覆盖节点时同时增加其最大值和标记；部分覆盖时递归修改子节点，再按上述等式更新。根节点没有遗漏的祖先标记，所以它的最大值就是答案。若以后扩展为任意子区间查询，则需要额外累加沿途标记，不能直接照搬普通无标记查询。

正确性证明

所有满足价差限制的集合都被某个候选窗口包含，因此最大窗口计数不会小于最优集合大小；任意候选窗口内的全部商品又构成合法集合，因此不会大于最优值。二者相等。

由 $v_i\le x\le v_i+k$ 与 $x-k\le v_i\le x$ 等价可知，每次区间加减恰好改变所有且仅有受该商品影响的窗口。差分初始化准确，线段树更新保持节点最大值不变量，故每次调价后的根值恰为所需答案。

题解代码

from bisect import bisect_left
import sys

input = sys.stdin.readline


class RangeAddMax:
    def __init__(self, values):
        self.n = len(values)
        self.maximum = [0] * (4 * self.n)
        self.tag = [0] * (4 * self.n)

        def build(node, left, right):
            if left == right:
                self.maximum[node] = values[left]
                return
            middle = (left + right) // 2
            build(node * 2, left, middle)
            build(node * 2 + 1, middle + 1, right)
            self.maximum[node] = max(self.maximum[node * 2], self.maximum[node * 2 + 1])

        build(1, 0, self.n - 1)

    def add(self, query_left, query_right, delta):
        maximum, tag = self.maximum, self.tag

        def update(node, left, right):
            if query_left <= left and right <= query_right:
                maximum[node] += delta
                tag[node] += delta
                return
            middle = (left + right) // 2
            if query_left <= middle:
                update(node * 2, left, middle)
            if query_right > middle:
                update(node * 2 + 1, middle + 1, right)
            maximum[node] = tag[node] + max(maximum[node * 2], maximum[node * 2 + 1])

        update(1, 0, self.n - 1)


def price_answers(prices, operations, k):
    values = sorted(set(prices) | {value for _, value in operations})
    position = {value: i for i, value in enumerate(values)}
    low = [bisect_left(values, value - k) for value in values]
    current = [position[value] for value in prices]
    difference = [0] * (len(values) + 1)
    for index in current:
        difference[low[index]] += 1
        difference[index + 1] -= 1
    counts = []
    running = 0
    for i in range(len(values)):
        running += difference[i]
        counts.append(running)
    tree = RangeAddMax(counts)
    for p, value in operations:
        p -= 1
        old, new = current[p], position[value]
        if old != new:
            tree.add(low[old], old, -1)
            tree.add(low[new], new, 1)
            current[p] = new
        yield tree.maximum[1]


def solve():
    n, k = map(int, input().split())
    prices = list(map(int, input().split()))
    q = int(input())
    operations = [tuple(map(int, input().split())) for _ in range(q)]
    for answer in price_answers(prices, operations, k):
        print(answer)


if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度：$O((n+q)\log(n+q))$。离散化与边界二分为 $O((n+q)\log(n+q))$，差分初始化和建树为 $O(n+m)$，每次修改为 $O(\log m)$。

空间复杂度：$O(n+q)$，包括离散化价格、全部修改、当前价格下标、差分数组和线段树。

易错点

$k=0$ 时统计的是同价商品的最大种数；改价是永久赋值，不是增加价格，也不是独立询问。必须将全部未来价格加入离散化；旧价与新价相同时可直接输出当前答案。

小结

• 免费操作先看不变量，付费操作再做下界与构造证明。
• 对半切割从最长段开始，让每一步变成匹配、强制切分或无解判断。
• 滑动窗口必须先证明成本单调，再用单调队列维护窗口内部的最优免检段。
• 动态价格问题可从“一个商品影响哪些窗口”反向建模，转成区间加与最大值维护。