拼多多 10.25 机考三题:车厢调序、绳段拆分与免检批次
- 轮次
- 笔试
- 时间
- 2026-10
- 来源
- 牛客网
《面试题目》
第 1 题:车厢调序耗电(中等·排序)
货运列车挂了 L 节车厢,自左向右记为第 1 至 L 节,第 t 节的卸货等级为 Bₜ,各节等级两两不同,目标是排成自左向右严格递增。站台备了两套器具:
- 小型调转轨道:挑出紧挨着的 2 节车厢,倒转它们的先后次序,每次耗电 1 单位。
- 三节回旋轨道:挑出紧挨着的 3 节车厢,整段倒序,配了加长摇柄和配重,完全不耗电。
两种设备用几次、谁先谁后、压在哪一段都能自由安排。求排成目标次序的最少耗电量。
输入:首行 Q(1 ≤ Q ≤ 10)组数;随后 Q 行,每行先给 L(1 < L < 10⁵)再给 L 个整数 Bₜ(0 ≤ Bₜ ≤ 10⁹,互不相等)。输出:每行一个整数,对应每组最少耗电。
样例:2 / 4 1 3 2 4 / 3 3 2 1,输出 1 和 0。第一组 1,3,2,4 用小型轨道倒转第 2、3 节即得 1,2,3,4,耗电 1;不耗电时只能交换第 1 与第 3 节、或第 2 与第 4 节,奇数位仍会是 1 和 2、而目标奇数位是 1 和 3,所以不可能为 0。第二组 3,2,1 用三节回旋轨道整段倒序直接得到 1,2,3,耗电 0。
第 2 题:绳段拆分判定(中等·贪心)
一根长度为 S 的绳子可以切任意多刀,也可以一刀不动。每次下刀挑出某一截(长度记作 y),沿正中分开,得到 ⌊y/2⌋ 与 ⌈y/2⌉ 两截;长度为 1 的一截无法再分。希望最后桌上正好摆着 K 截,长度分别是 B₁…B_K,每一截都必须是切出来的一整根,不能把几截接起来,桌上也不许多留任何一截。判断能否做到。
输入:首行 Q(0 < Q ≤ 50);每组占两行,前一行 S、K(1 ≤ S ≤ 10¹⁴,1 ≤ K ≤ 10⁵),后一行 K 个整数 Bᵢ(1 ≤ Bᵢ ≤ 10⁹)。输出:每组一行 YES 或 NO。
样例:3 / 7 3 / 2 2 3 / 6 3 / 2 2 2 / 9 2 / 4 6,输出 YES、NO、NO。7 先切成 3 和 4,再把 4 切成 2 和 2,得到 2,2,3;6 只能先切成 3 和 3,再动其中一个 3 只能得到 1 和 2,永远变不成 2,2,2;4 加 6 是 10,与起始长度 9 不等,切割改变不了长度之和。
第 3 题:货物免检批次(困难·滑动窗口)
传送带上依次摆着 M 件待查的货,第 i 件的检查耗时是 Pᵢ、要走档位 Gᵢ(只取 0 或 1)。挑出一段中间不间断、至少含一件的货,按原先后查完:刚开查时设备停在最前面那件的档位上,往后只要相邻两件档位不同,就要再花 S 的时间拨档。同一段里最多能用一次免检,免检盖住这一段内部连续的至多 W 件,被盖住的检查耗时改成 0;这些货仍留在原位过机器,档位一个不改,该付的拨档时间照付。求总耗时不超过 U 时,这一段最长能有多少件。
输入:首行 M、W、U、S(1 ≤ M ≤ 2×10⁵,1 ≤ W ≤ M,0 ≤ U ≤ 10¹⁸,0 ≤ S ≤ 10⁹);第二行 M 个 Pᵢ(1 ≤ Pᵢ ≤ 10⁹);第三行 M 个 Gᵢ∈{0,1}。输出:一个整数。
样例:5 1 6 3 / 2 4 1 5 2 / 0 0 0 1 1,输出 3。取最左边三件,检查耗时 2+4+1=7,免检只能盖住 1 件,盖住中间的 4 后还剩 3;三件档位都是 0 不用拨设备,总耗时 3 ≤ 6。再多拿一件就超了。
《参考解析》
车厢题:先看清「免费操作」到底改了什么,答案不是逆序对的奇偶。 三节回旋轨道把相邻三节整段倒序,中间那节原地不动,所以它等价于交换下标相差 2 的两节,而且不耗电。反复使用它,等价于可以在所有奇数下标之间任意重排、在所有偶数下标之间任意重排,但它永远无法把一节车厢从奇数位挪到偶数位。而小型调转轨道交换的是相邻两节(下标差 1),恰好是唯一能改变「位置奇偶」的手段,每用一次耗电 1。
于是问题变成:把卸货等级离散成名次(从 0 数起),名次为 p 的车厢最终必须停在下标 p,因此名次的奇偶必须和它所在下标的奇偶一致。设停在偶数下标上、名次却是奇数的车厢有 x 节,那么奇数下标上也恰好有 x 节名次为偶数的车厢(两侧数量守恒)。相邻对调一次最多把这样一对车厢同时换到正确的一侧,三节倒序根本改变不了 x,所以耗电至少是 x。这个下界可以达到:x > 0 时先用免费交换把一节放错的偶数位车厢和一节放错的奇数位车厢挪到下标 0 和 1,做一次相邻对调,x 减 1;x 归零后两侧各自恰好都在正确的奇偶类里,再用免费交换把每一侧排成递增即可。所以最少耗电就是 x/2,也就是统计「下标奇偶与名次奇偶不一致」的车厢数再除以 2。
实现只要排序 + 一次线性扫描:order = sorted(range(L), key=B.__getitem__),rank[order[p]] = p,然后 wrong += (idx & 1) != (rank[idx] & 1),输出 wrong // 2。复杂度每组 O(L log L)。用样例自查一遍:1,3,2,4 的名次是 0,2,1,3,下标 1 对应名次 2(不一致)、下标 2 对应名次 1(不一致),x = 2,答案 1,与样例一致。注意不要掉进「答案只可能是 0 或 1」的坑——那是只考虑置换奇偶性的结论,忽略了「跨奇偶类需要额外次数」;例如 4,3,2,1 的逆序对是 6(偶),但四个位置的名次奇偶全部错位,答案是 2 而不是 0。
绳段题:贪心之所以成立,是因为短段永远拼不出长段。 切割是自顶向下的,任何目标段都只能由某个更长的段分裂而来,所以处理顺序只能是「按长度从大到小」。维护两个大根堆:一个放当前手里的段(初始只有 S),一个放目标段(降序)。每次比两个堆顶——相等就一起弹出,这一段正好对上、不再往下切;当前段更大就按 x/2 与 (x+1)/2 切成两段压回堆里;当前段更小说明目标里有一段比现存所有段都长,直接判 NO。两个堆都空而目标堆还有剩余,同样 NO。
三个必须单独判的边界:目标长度之和必须等于 S(切割不改变总和,这一条能在 O(K) 内砍掉大量无解样例);目标里出现 0 或负数直接否;还要防「切出来的段数已经超过剩余目标数」——如果堆里的段数比待匹配的目标还多,说明必定会剩下多余的一截,可以提前返回 NO。剪枝加上之后,每次切割使段数加 1 且不超过 K,因此至多切 K−1 次,总复杂度 O(K log K)。Python 里用 heapq 存负数模拟大根堆即可。
免检批次:把「一次免检」翻译成窗口内的一段最大子段和。 固定一段区间 [l, r] 后,总耗时 = 区间检查耗时之和 − 免检段耗时之和 + 拨档次数 × S,三项都能用前缀和 O(1) 求出:检查耗时前缀和、拨档次数的前缀(走到第 i 件已经拨过几次,相邻档位不同则 +1),免检段就是「区间内长度不超过 W 的连续子段和最大值」。因为所有 Pᵢ 都是正数,能盖住的件数一定取满 min(W, 段长),并且要选这一段里和最大的那一截。
最难的是这个不定长区间内「长度不超过 W 的最大子段和」怎么快。做法是只枚举右端点:对每个 r,新增一个以 r 结尾、长度恰好为 W 的窗口(起点 r−W+1),用一个单调队列维护「当前左端点允许范围内这些窗口和」的最大值——队列里存起点下标,对应的窗口和递减,队头就是可用的最大免检额度,左端点右移时把起点小于当前左端点的窗口弹出队首。免检额度因此可以 O(1) 取到。
剩下的部分用双指针:固定右端点把左端点往右移时,免掉的最大额度只会持平或变小(可用窗口集合只减不增),拨档次数也不会变多,所以总耗时关于左端点是单调的,可以用「右端扩、左端不满足条件就缩」的标准滑窗。免检段必须连续,取「区间里最大的 W 个 Pᵢ」是错的;拨档次数按原序列算,免检段内部与两侧的档位变化照旧计入。左右端点与队列里的每个下标都只进出一次,总复杂度 O(M);注意 U 最大 10¹⁸、M 最大 2×10⁵,所有累加量都要用 64 位整数。
三题连起来看这场机考的取向:没有一道需要高级数据结构,全是「把一道文字题准确翻译成一个标准模型」。车厢题考的是能不能看清免费操作的真实作用范围(这就是为什么先写出「三节倒序 = 交换下标差 2」这一句比直接写代码重要),绳段题考的是贪心顺序为什么唯一,免检题考的是能不能把带条件的区间最值化归成滑窗加单调队列。考场上最省时间的顺序是先做前两题(各 20 分钟内可完成),把第三题的窗口内最大子段和留足时间推导。