✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🤖 内容包含AI辅助生成，题解和代码均经过多轮验证，有问题欢迎评论

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

拼多多-2026.04.12

题目总览

题号	题名	主要做法	难度
1	赛道计时	差分统计	简单
2	站位安排	二分答案	中等
3	能源回收	前缀和 + 双向枚举	困难
4	魔法树水晶	树上 DAG 动态规划	困难

这套拼多多前两题比较像常规机考节奏，后两题明显更考建模。第三题要把来回折返的代价整理清楚，第四题则要把树上的大小约束转成稳定的转移关系。

1. 小兰的赛道计时

问题描述

小兰来到一座特殊的赛车场。这里一共有 条平行赛道，每条赛道的总长度都是 米。

整条赛道会被切成 段长度为 的小段，从起点开始依次编号为第 段到第 段。
第 段中，只有赛道编号落在区间 内的赛道铺设了水泥路面，其余赛道在这一段都是泥地。

赛车在两种路面上的速度不同：

• 水泥地： 米每秒
• 泥地： 米每秒

小兰可以任选一条赛道起跑，并且一旦选定赛道，途中不能变道。
她想让到达终点的总时间尽量短；如果有多条赛道都能达到最短时间，则选择编号最小的那一条。

请输出最短用时以及对应的赛道编号。

输入格式

第一行输入两个整数 ，表示赛道条数和每条赛道的长度。

接下来 行，第 行输入两个整数 ，表示第 段中铺设水泥地的赛道编号范围。

输出格式

输出一行两个整数，分别表示最短时间和对应的赛道编号。

样例输入

3 2
1 2
2 3

样例输出

2 2

数据范围

• 
• 

样例说明

• 样例1：第 条赛道经过 段水泥地和 段泥地，总时间是 。第 条赛道两段都是水泥地，总时间是 。第 条赛道同样是 秒，所以答案是 2 2。

题解

一条赛道的总长度固定都是 ，所以真正影响时间的，只有它经过了多少段水泥地。

设某条赛道经过了 段水泥地，那么：

• 这 段每段耗时 秒
• 剩下的 段每段耗时 秒

于是总时间就是：

也就是说，总时间越短，等价于该赛道经过的水泥段数越多。

因此问题变成：

• 对每条赛道，统计它被多少个区间 覆盖
• 找到覆盖次数最大的赛道
• 若有并列，取编号最小的赛道

这正好可以用差分数组完成。

对于每个区间 ：

• diff[l_i] += 1
• diff[r_i + 1] -= 1

然后做一次前缀和，就能得到每条赛道的水泥段数量。

设最大覆盖次数为 best，对应的最小赛道编号为 pos，那么答案就是：

复杂度分析

• 时间复杂度：
• 空间复杂度：

参考代码（Python）

import sys

input = lambda: sys.stdin.readline().strip()


def solve() -> None:
    # Read input in ACM mode and build the answer directly.
    n, m = map(int, input().split())
    diff = [0] * (n + 3)

    for _ in range(m):
        l, r = map(int, input().split())
        diff[l] += 1
        diff[r + 1] -= 1

    cur = 0
    best = -1
    pos = 1
    for i in range(1, n + 1):
        cur += diff[i]
        if cur > best:
            best = cur
            pos = i

    print(2 * m - best, pos)


if __name__ == "__main__":
    # Standard ACM entry.
    solve()

2. 小兰的站位安排

问题描述

小兰正在安排一场演出的站位。舞台上一共有 个可用站位，第 个站位的坐标为 。

现在有 位表演者需要上台，且必须恰好选择 个站位给他们使用。
为了避免站得太近造成舞台效果互相干扰，小兰 把一套安排方案的稳定程度定义为：

• 任意两名表演者之间距离的最小值

请你求出，这个最小值最大可以达到多少。

输入格式

第一行输入一个整数 ，表示测试数据组数。

对于每组测试数据：

• 第一行输入两个整数
• 第二行输入 个整数

输出格式

对于每组数据输出一行，一个整数，表示最大化后的最小距离。

样例输入

1
3 2
1 6 8

1
6 4
24 3 42 15 7 30

1
5 3
10000 10 20000 1 19999

样例输出

7

12

9999

数据范围

• 
• 
• 

题解

这是一个很典型的“最大化最小值”问题。

如果我们猜一个答案 d，问题就变成：

• 能不能从这些站位里选出 个
• 使得任意相邻已选站位之间的距离都至少为 d

这个判定是容易做的。

先把所有站位坐标排序。
然后贪心地从左到右选：

• 先选最左边的站位
• 之后每次尽量选“与上一个已选站位距离至少为 d 的最左站位”

如果最终能选出至少 个站位，说明这个 d 可行；否则不可行。

为什么这样贪心是对的？

• 对于固定的最小距离要求 d，每次尽量选更靠左的位置，只会给后面留下更多可选空间
• 因此它是判定可行性的最优策略

于是答案具有单调性：

• 若 d 可行，则所有更小的距离也都可行
• 若 d 不可行，则所有更大的距离也都不可能可行

所以可以在答案区间上二分。

复杂度分析

设单组数据有 个站位。

• 排序复杂度：
• 每次判定复杂度：
• 二分次数：

总复杂度为 。

参考代码（Python）

import sys

input = lambda: sys.stdin.readline().strip()


def can_place(pos, need, dist):
    count = 1
    last = pos[0]
    for x in pos[1:]:
        if x - last >= dist:
            count += 1
            last = x
            if count >= need:
                return True
    return False


def solve() -> None:
    # Read input in ACM mode and build the answer directly.
    t = int(input())
    out = []
    for _ in range(t):
        k, n