Zero2Leetcode

大厂真题 / 拼多多

拼多多 8.2 笔试真题 - 通用（研发/算法）

本场考试概述

考试时间：2026年8月2日

考试岗位：通用（研发/算法）

难度评级：中等偏难

考点分析：

  • 第一题：前缀和与首次出现位置（难度简单）
  • 第二题：贪心构造与可行性判定（难度中等）
  • 第三题：分层图与 Dijkstra 最短路（难度中等）
  • 第四题：环上独立集覆盖与下界证明（难度困难）

建议策略：

  • 第一题是典型的“数量相等”模型，把两类元素分别赋值为 $1$ 和 $-1$ 后线性扫描即可，应优先拿下
  • 第二题不要只凭局部最小值直接贪心；每次试放后必须判断剩余多重集合能否接在当前末尾之后
  • 第三题的关键是把“优惠券是否使用”纳入状态；第四题则要分别寻找单点、相邻点和整张环带来的必要下界

第 1 题：平衡队伍

题目描述

$n$ 名队员排成一列，每名队员属于 A、B 两种类型之一。教练要选择一段连续区间；如果其中 A 类与 B 类队员数量相同，就称其为平衡队伍。

求平衡队伍的最大长度；如果不存在非空的平衡区间，输出 $0$。

输入第一行是整数 $n$，第二行是长度为 $n$ 且仅含 A、B 的字符串 $s$。

数据范围：$1 \leq n \leq 2 \times 10^5$。

样例 1

输入

4
ABAB

输出

4

整个序列中两种队员各有两名，因此答案为 $4$。

样例 2

输入

3
AAA

输出

0

样例 3

输入

5
AAABB

输出

4

思路分析

第一步：把计数相等转成区间和为零

给 A 赋值 $1$，给 B 赋值 $-1$。一段区间的元素和就是该区间内 A 的数量减去 B 的数量，因此平衡条件等价于区间和为 $0$。

如果直接枚举左右端点，需要 $O(n^2)$ 时间。为了快速得到区间和，引入前缀和：令 $pre_i$ 表示前 $i$ 个位置的权值和，并令 $pre_0=0$。区间 $[l,r]$ 平衡当且仅当

\[pre_r-pre_{l-1}=0,\]

也就是 $pre_r=pre_{l-1}$。

第二步：寻找距离最远的相同前缀和

问题已经转化成：在前缀和序列中，寻找值相等且下标距离最大的一对位置。

从左向右扫描。对于每个前缀和值，只记录它第一次出现的位置。以后再次遇到相同值时，用当前位置减去最早位置更新答案。保留更晚的位置不会产生更长区间，所以没有必要。

前缀和一定落在 $[-n,n]$，既可以使用哈希表，也可以使用长度 $2n+1$ 的数组并加上偏移量 $n$。下面使用数组，常数更小。

第三步：处理空前缀与无解情况

扫描前要记录 first[n] = 0，表示和为 $0$ 的空前缀出现在位置 $0$。否则会漏掉从第一个位置开始的平衡区间。

答案初值设为 $0$。如果没有任何相同前缀和形成正长度区间，最终自然输出 $0$，无需额外特判。

以 AAABB 为例，前缀和依次为 $0,1,2,3,2,1$。值 $1$ 最早出现在下标 $1$，又在下标 $5$ 出现，于是得到长度 $5-1=4$。

题解代码

import sys
input = sys.stdin.readline


def solve():
    n = int(input())
    s = input().strip()

    first = [-1] * (2 * n + 1)
    offset = n
    first[offset] = 0

    prefix = 0
    answer = 0
    for i, ch in enumerate(s, 1):
        prefix += 1 if ch == "A" else -1
        index = prefix + offset
        if first[index] == -1:
            first[index] = i
        else:
            answer = max(answer, i - first[index])

    print(answer)


solve()

复杂度分析

时间复杂度：$O(n)$，每名队员只处理一次。

空间复杂度：$O(n)$，用于保存每种前缀和的首次出现位置。

边界情况

  • $n=1$ 时不可能选出人数相等的非空区间，答案为 $0$
  • 整个字符串平衡时，需要依靠预先记录的空前缀得到答案 $n$
  • 全部字符相同时，答案保持为 $0$

第 2 题：评价展示序列

题目描述

商品共有 $n$ 条评价，每条评价的星级是 $1$ 到 $5$ 之间的整数。现在要重新排列这些评价，使任意两条相邻评价的星级不同。

如果合法排列存在，输出字典序最小的排列；否则输出 -1。

两个等长序列按字典序比较：从左向右找到第一个不同的位置，该位置数值较小的序列字典序更小。

输入第一行是整数 $n$，第二行是 $n$ 个星级 $a_i$。

数据范围：$1 \leq n \leq 10^5$，$1 \leq a_i \leq 5$。

样例 1

输入

5
1 1 1 2 3

输出

1 2 1 3 1

样例 2

输入

4
1 1 1 1

输出

-1

样例 3

输入

6
5 5 3 5 3 1

输出

1 5 3 5 3 5

思路分析

第一步：为什么不能只选当前最小值

为了让字典序最小，直觉上应在每一位选择尚未用完、且不等于上一位的最小星级。但直接这样做可能过早消耗少数类元素，导致数量最多的星级在后面无法被隔开。

因此，每次选择候选值后，要判断剩余元素能否组成一个合法后缀。只要后缀仍可行，就可以立即确定这个候选；因为字典序首先由当前位决定，更大的候选不可能更优。

第二步：推导剩余局面的可行条件

设还剩 $m$ 个元素，上一位星级为 last。设剩余出现次数最多的星级为 $x$，其数量为 $c$。

要隔开 $c$ 个相同的 $x$，至少需要 $c-1$ 个其他元素，所以首先必须满足

\[2c-1 \leq m.\]

更精确地说，对任意星级 $v\ne\text{last}$，它至多占后缀的奇数位，因此必须满足 $2c_v\le m+1$；对 $v=\text{last}$，后缀首位不能再放它，因此必须满足 $2c_v\le m$。这组条件也是充分的：始终优先放当前剩余数量最多且不同于上一位的星级，就能把各星级依次放入允许的位置。

如果恰好有 $2c-1=m$，后缀只能严格交替成

\[x,\ *,\ x,\ *,\ \ldots,\ *,\ x.\]

此时后缀必须以 $x$ 开头。如果 $x=\text{last}$，它无法接在已有前缀之后，局面不可行。因此完整判据为：

  • 若 $2c-1>m$，不可行
  • 若 $2c-1=m$ 且 $x=\text{last}$，不可行
  • 其他情况可行

星级只有五种，所以每次检查计数数组只需常数时间。

第三步：逐位试放并保证字典序最小

当前位依次尝试星级 $1,2,\ldots,5$：

  1. 跳过计数为零或等于上一位的值
  2. 暂时把该值计数减一
  3. 用上述判据检查剩余后缀
  4. 若可行，就固定当前位；否则恢复计数并尝试更大的值

每一位选择的都是“仍能完成整个序列”的最小值。对任意另一合法答案，若它第一次与本算法不同，本算法在该位置选择的值一定更小，因此所得序列就是全局字典序最小解。

开局可以把 last 设为 $0$，因为它不可能与任何真实星级相等。也应先对完整多重集合做一次可行性检查；若失败，直接输出 -1。

题解代码

import sys
input = sys.stdin.readline


def feasible(count, remaining, last):
    if remaining == 0:
        return True

    max_count = 0
    max_value = 0
    for value in range(1, 6):
        if count[value] > max_count:
            max_count = count[value]
            max_value = value

    if 2 * max_count - 1 > remaining:
        return False
    if 2 * max_count - 1 == remaining and max_value == last:
        return False
    return True


def solve():
    n = int(input())
    stars = list(map(int, input().split()))

    count = [0] * 6
    for value in stars:
        count[value] += 1

    if not feasible(count, n, 0):
        print(-1)
        return

    answer = []
    last = 0
    for position in range(n):
        for value in range(1, 6):
            if count[value] == 0 or value == last:
                continue

            count[value] -= 1
            remaining = n - position - 1
            if feasible(count, remaining, value):
                answer.append(value)
                last = value
                break
            count[value] += 1

    print(*answer)


solve()

复杂度分析

时间复杂度：$O(n)$。每个位置至多尝试 $5$ 个值，每次判定也只扫描 $5$ 种星级。

空间复杂度：$O(n)$，答案数组占 $O(n)$；计数数组只占常数空间。

边界情况

  • 只有一条评价时，它本身就是答案
  • 某星级数量超过 $\lceil n/2 \rceil$ 时一定无解
  • 数量最多的星级恰好占满所有奇数位时，要特别检查它是否与已构造前缀的末尾相同
  • 输入次序不影响答案，只需要保留五种星级的出现次数

第 3 题：多多送快递

题目描述

$n$ 个城市之间有 $m$ 条有向运输线路。每条线路由城市 $u$ 指向城市 $v$，邮费为正整数 $w$。

商品要从城市 $1$ 送到城市 $n$。现在有一张免邮券，可以把所经过的任意一条线路的邮费变为 $0$；也可以不使用。求从城市 $1$ 到城市 $n$ 的最小总邮费。如果无法到达，输出 -1。

输入第一行是 $n,m$，接下来 $m$ 行每行给出 $u,v,w$。

数据范围：$2 \leq n \leq 10^5$，$0 \leq m \leq 2 \times 10^5$，$1 \leq u,v \leq n$，$1 \leq w \leq 10^4$。

样例

输入

4 4
1 2 2
1 3 5
2 4 3
3 4 1

输出

1

把免邮券用在边 $1\to3$ 上，再支付边 $3\to4$ 的邮费 $1$，总费用最小。

思路分析

第一步：同一城市需要区分两种状态

普通最短路只需记录“到达城市 $u$ 的最小花费”。但本题中，以相同花费到达同一城市时，手里是否还保留免邮券会影响后续决策，二者不能合并。

因此把每个城市拆成两层：

  • 状态 $(u,0)$：到达 $u$ 时尚未使用免邮券
  • 状态 $(u,1)$：到达 $u$ 时已经使用免邮券

这样共有 $2n$ 个状态。

第二步：把原图边转换为状态转移

对于原图中的有向边 $u\to v$，边权为 $w$：

  • 从 $(u,0)$ 正常付费到 $(v,0)$，代价为 $w$
  • 从 $(u,1)$ 正常付费到 $(v,1)$，代价为 $w$
  • 从 $(u,0)$ 使用免邮券到 $(v,1)$，代价为 $0$

不存在从已用券层返回未用券层的边，也不存在第二次免费跨层，所以这个模型天然保证券至多使用一次。

第三步：在分层图上运行 Dijkstra

所有转移边权都非负，可以从 $(1,0)$ 出发运行 Dijkstra。分层图无需显式建立：遍历城市 $u$ 的原始出边时，根据当前状态实时执行上述一到两种松弛即可。

最终答案是

\[\min(dist_{n,0},dist_{n,1}),\]

因为未使用券到达终点也属于合法方案。若两者都仍为无穷大，则输出 -1。

直接枚举哪条边免费，再为每条边单独运行最短路，会产生约 $O(m^2\log n)$ 的代价；分层图只把点数和边数扩大常数倍。

题解代码

import sys
from heapq import heappop, heappush

input = sys.stdin.readline
INF = 10**30


def solve():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v, weight = map(int, input().split())
        graph[u].append((v, weight))

    dist = [[INF, INF] for _ in range(n + 1)]
    dist[1][0] = 0
    heap = [(0, 1, 0)]

    while heap:
        current_dist, u, used = heappop(heap)
        if current_dist != dist[u][used]:
            continue

        for v, weight in graph[u]:
            paid_dist = current_dist + weight
            if paid_dist < dist[v][used]:
                dist[v][used] = paid_dist
                heappush(heap, (paid_dist, v, used))

            if used == 0 and current_dist < dist[v][1]:
                dist[v][1] = current_dist
                heappush(heap, (current_dist, v, 1))

    answer = min(dist[n])
    print(-1 if answer == INF else answer)


solve()

复杂度分析

时间复杂度：$O((n+m)\log n)$。分层后的状态数和转移数都只是原图的常数倍。

空间复杂度：$O(n+m)$，用于邻接表、距离数组与优先队列。

边界情况

  • 图是有向图，不能把线路反向加入邻接表
  • 自环与重边可以直接交给 Dijkstra 处理
  • 路径费用可能超过 $32$ 位整数范围；Python 整数可自动扩展
  • 终点不可达时，两层距离都会保持为无穷大

第 4 题：环形分厂协调补货

题目描述

$n$ 个分仓沿环形物流干线排列，编号为 $1$ 到 $n$。除相邻编号外，分仓 $1$ 与分仓 $n$ 也相邻。分仓 $i$ 需要补货 $a_i$ 次。

每个补货班次可以选择若干分仓，并让每个被选分仓完成一次补货。同一班次内，任何两个相邻分仓都不能同时被选择。每个分仓必须恰好被选择 $a_i$ 次。

求完成所有需求所需的最少班次数。

输入第一行是测试用例数 $T$。每组数据先给出 $n$，再给出 $n$ 个非负整数 $a_i$。保证所有测试用例的 $n$ 之和不超过 $2\times10^6$。

数据范围：$1 \leq n \leq 2\times10^5$，$0 \leq a_i \leq 10^9$，且 $\sum n \leq 2\times10^6$。

样例 1

输入

1
3
1 1 1

输出

3

三个分仓两两相邻，每班最多选择一个分仓。

样例 2

输入

1
4
3 0 3 0

输出

3

分仓 $1$ 和 $3$ 不相邻，可以在三个班次中始终同时选择二者。

样例 3

输入

1
6
1 2 3 1 2 3

输出

5

例如可以依次选择分仓集合 ${2,5}$、${1,3,5}$、${3,6}$、${3,6}$、${2,4,6}$，每个集合都是环上的独立集，累计次数恰好满足需求。

思路分析

每个班次选择的是环上的一个独立集。题目等价于：用尽量少的独立集对各顶点进行带重数覆盖，使顶点 $i$ 总共出现 $a_i$ 次。

关键不是模拟每一个班次，而是找到班次数 $k$ 必须满足的全部瓶颈。

第一步：单个分仓给出的下界

同一分仓在一个班次中最多被补货一次，所以至少需要

\[L_1=\max_i a_i\]

个班次。

第二步：相邻分仓给出的下界

任意相邻的两个分仓不能出现在同一班次。它们的补货次数必须占用互不重合的班次，因此

\[L_2=\max_i(a_i+a_{i+1}),\]

其中下标按环处理，即还要检查 $a_n+a_1$。

事实上，当 $n$ 为偶数时，环是二分图，这类相邻约束已经足够；$L_2$ 也自然不小于 $L_1$。

第三步：整张环的容量下界

一个长度为 $n$ 的环，其独立集最多包含 $\lfloor n/2\rfloor$ 个顶点。设总需求为

\[S=\sum_{i=1}^{n}a_i,\]

则每个班次最多完成 $\lfloor n/2\rfloor$ 次补货，因而还需要

\[L_3=\left\lceil\frac{S}{\lfloor n/2\rfloor}\right\rceil\]

个班次。

这条约束主要在奇数环上发挥作用。例如三角形每班只能选择一个点，单看相邻两点之和无法覆盖三个点的总需求。

第四步：为什么取三条下界的最大值就够

这里可以直接使用环图的整数加权着色定理：偶环的加权色数等于最大相邻需求和；奇环 $C_{2h+1}$ 的加权色数等于最大相邻需求和与 $\lceil S/h\rceil$ 中的较大者。每个班次对应一种颜色，同色顶点构成独立集，而顶点 $i$ 需要获得 $a_i$ 种颜色，因此本题正是该定理的加权着色模型。

该定理不仅给出必要下界，也保证整数需求可以分解为相应数量的独立集。若某个分解让顶点出现次数超过需求，还可以从部分独立集中删去该顶点；删除不会破坏独立性，所以能进一步调整为恰好出现 $a_i$ 次。

因此，只要班次数 $k$ 同时满足

\[k\geq L_1,\qquad k\geq L_2,\qquad k\geq L_3,\]

就能把每个分仓的 $a_i$ 次需求安排到 $k$ 个班次中，并保证每个班次选择的都是独立集。因此答案就是三者最大值。这里 $L_1$ 对 $n\ge2$ 已包含在 $L_2$ 中，代码保留它只是为了让三个下界的含义更直观。

对于偶数环，$L_3$ 不会比相邻约束更强。因为可以把环边交替分成两组完美匹配，而任意一组匹配上的相邻需求和之和都是 $S$；若每条边的需求和均不超过 $L_2$，便有 $S\leq(n/2)L_2$。奇数环少了二分图结构，整体容量约束正好补足这一缺口。

第五步：单点环必须特判

$n=1$ 时没有其他分仓与它冲突，每班都能选择唯一分仓，答案直接是 $a_1$。此时 $\lfloor n/2\rfloor=0$，若套用容量公式会发生除零。

计算其余情况时只需一次线性扫描，求总和、单点最大值和相邻两点之和最大值，再做一次向上取整：

\[\left\lceil\frac{S}{h}\right\rceil=\left\lfloor\frac{S+h-1}{h}\right\rfloor,\]

其中 $h=\lfloor n/2\rfloor$。

题解代码

import sys
input = sys.stdin.readline


def minimum_shifts(demand):
    n = len(demand)
    if n == 1:
        return demand[0]

    total = sum(demand)
    max_single = max(demand)
    max_adjacent = 0

    for i in range(n):
        adjacent_sum = demand[i] + demand[(i + 1) % n]
        max_adjacent = max(max_adjacent, adjacent_sum)

    capacity = n // 2
    capacity_bound = (total + capacity - 1) // capacity
    return max(max_single, max_adjacent, capacity_bound)


def solve():
    test_cases = int(input())
    answers = []

    for _ in range(test_cases):
        n = int(input())
        demand = list(map(int, input().split()))
        answers.append(minimum_shifts(demand))

    print("\n".join(map(str, answers)))


solve()

复杂度分析

时间复杂度：每组为 $O(n)$；所有测试用例合计为 $O(\sum n)$。

空间复杂度：每组为 $O(n)$，用于保存当前需求数组。

边界情况

  • $n=1$ 时答案是唯一分仓的需求量，必须避免容量公式除零
  • 所有 $a_i=0$ 时答案为 $0$
  • 必须计算首尾相邻的一对 $a_n+a_1$
  • 总需求可能达到 $10^{14}$ 量级，实现时需要使用足够宽的整数类型
  • $n=2$ 时两个分仓互相冲突，答案退化为 $a_1+a_2$

小结

  • 第一题把两类元素分别映射为 $1$ 和 $-1$，将“数量相等”转化为“相同前缀和”，只保留每个前缀和的最早位置
  • 第二题逐位选择最小星级，并用“最大频次是否还能被其他元素隔开”的充要条件保护后续可行性
  • 第三题把每个城市拆成“未用券”和“已用券”两层，在分层图上一次 Dijkstra 即可处理任意一条边免费
  • 第四题从单点、相邻点和整张环三个角度推导班次数下界，利用环图结构说明三条约束的最大值就是最优答案