拼多多后端研发笔试:逆序对奇偶性、双堆切绳与滑动窗口免检
- 轮次
- 笔试
- 时间
- 2026-10
- 来源
- 牛客网
《面试题目》
算法题(四道)
- 列车调转顺序:给定一个表示列车优先级的排列,要求调整为升序。可以选择相邻两个车厢调转顺序,消耗 1 单位电;也可以选择相邻三个车厢调转顺序,消耗 0 单位电。求最小消耗。
- 分解绳子:给定绳子长度 L 和需要切出的目标长度序列,每次只能把当前的一段从正中间切开,分为 x/2 上取整与 x/2 下取整两段。判断能否最终得到这组目标长度,不允许剩下多余的绳子。
- 货物检查耗时:n 件货物,第 i 件的检查时间为 a_i、模式为 c_i(只取 0 或 1),相邻两件模式不同时额外消耗固定的切换时间 D。最多有一次免检机会,可以选一段连续且长度不超过 K 的货物免去其检查时间,模式切换仍按原序列计算。求总耗时不超过 B 的情况下,最多能连续检查多少件货物。样例:K=3、B=9、D=5,检查时间 3 4 5 6 7 8 3 3 5,模式 0 0 0 0 1 1 0 0 0。
- 橘子问题:有 n 种橘子,给定初始价格;有 q 次修改操作,每次修改一种橘子的价格。每次修改后,求最多能选出多少种橘子,使得选出的橘子中最大值与最小值之差不超过 k。
《参考解析》
列车题:0 成本的三种轮换是偶置换,答案只有 0 和 1 交换相邻两个车厢就是一次相邻对换,改变排列奇偶性;交换相邻三个车厢等价于两次相邻对换,是偶置换,不改变逆序对个数的奇偶性。而在 n≥3 时相邻三元轮换足以生成整个交错群,所以逆序对为偶数时全程可以只用 0 成本操作排好,为奇数时先花 1 单位电做一次相邻交换、之后都落在偶置换里。答案因此是逆序对数的奇偶性,不是逆序对数本身。求逆序对用归并排序或树状数组,O(n log n);n 上到 1e5 时内层枚举的 O(n²) 必然超时,值域很大时还要先离散化再上树状数组。
切绳题:两个大根堆从最大段往下对消 切断是自顶向下的,任何目标段都只能由某个更长的段分裂而来,所以按长度从大到小处理是唯一可行的顺序。维护两个大根堆,一个放当前所有段(初始只有 L),一个放目标段。每次比较两个堆顶:相等就一起弹出,这段正好对上、不再往下切;当前段更大就按上取整与下取整切成两段压回堆里;当前段更小说明目标里有一段比现存任何段都长,直接判不可能。两个堆都空而目标堆还有剩余,同样不可能。复杂度 O(m log m),m 是过程中产生的段数。边界要单独处理:目标段之和必须等于 L,目标里出现 0 或负数直接否,x=1 时切出来是 0 长度,也要判掉。
货物检查题:前缀和加滑窗,免检段是窗口内长度不超过 K 的最大子段和 窗口内的总耗时 = 检查时间之和 − 免检段之和 + 模式切换次数 × D,三项都能前缀和维护,难点是不定长窗口下「长度不超过 K 的最大子段和」怎么快速求。枚举右端点 r 向右扩,用单调队列维护窗口内前缀和的滑动最小值:免检段取 [l, r] 内长度不超过 K、和最大的子段,等价于在窗口里找 max(P[i]) 与 min(P[j])(i − j ≤ K)的差,左端收缩时把过期下标从队首弹掉,整体 O(n)。两个易错点:免检段必须连续,取「最大的 K 个 a_i」是错的;模式切换按原序列算,免检段两侧的模式差仍然要计入。
橘子题:单点修改下的定长值域窗口最大和 每次修改后重排是 O(q·n log n),考场写「计数字典加堆」那个方向也过不了。把它变成值域上的定长窗口:把所有出现过的价格离散化,设 cnt[v] 为价格 v 的橘子个数,答案就是覆盖 [v, v+k] 这段值域的 cnt 之和的最大值。单点修改只影响 cnt 的一个位置,也就只影响左端点落在 [p−k, p] 里的那些窗口,它们在排序后的窗口数组里是一段连续下标,用线段树做区间加加全局最大值即可,每次 O(log n)。这题真正难的不是数据结构,而是看出「答案是一个滑动的值域窗口」和「一次修改影响连续一段窗口」。