✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

滴滴-2026.03.22-第二套

1. 小基 的前后仓差异匹配

问题描述

小基 在整理一条长度为 的货物记录数组 。

对于每个位置 ：

• 把区间 记作前缀 ；
• 把区间 记作后缀 。

她定义了两个量：

• 前缀差异度

• 后缀差异度

现在对每个前缀 （），都要在它右边找一个互不重叠的后缀 ，也就是要求 ，并让：

尽可能小。

请你计算下面这个总和：

输入格式

第一行输入一个整数 ，表示数组长度。

第二行输入 个整数 ，表示数组元素。

输出格式

输出一行一个整数，表示题目要求的总和。

样例输入

4
1 3 2 4

样例输出

3

数据范围

样例	解释说明
样例 1	前缀差异度依次是 ，后缀差异度依次是 。对前缀 分别取右侧最接近值后，贡献是 ，总和为 。

题解

先把两个量写开就会发现，这题其实分成了两步：

1. 先快速求出所有 和 ；
2. 对每个 ，去右边的后缀差异度里找最接近的值。

一、怎么在线性时间求出 和

先看前缀。

设前缀 的最大值是 ，前缀和是 ，那么：

所以从左到右扫一遍，维护：

• 当前前缀最大值；
• 当前前缀元素和。

就能在 时间求出全部 。

后缀完全一样。设后缀 的最大值是 ，后缀和是 ，则：

从右到左扫一遍即可。

二、右边最接近的 怎么找

当我们枚举到某个前缀 时，只允许选择 ，也就是只能从集合：

里找最接近 的值。

这提示我们可以从右往左处理：

• 枚举到 之前，先把 加进数据结构；
• 这样数据结构里始终维护着所有合法的右侧后缀差异度。

接下来只要支持两件事：

1. 插入一个值；
2. 查询某个值的前驱和后继。

那么最优答案一定在这两个候选里产生。

三、为什么只看前驱和后继就够了

把当前要匹配的值记成 。

在一个有序集合里：

• 所有小于等于 的值中，离它最近的一定是最大的那个，也就是前驱；
• 所有大于等于 的值中，离它最近的一定是最小的那个，也就是后继。

所以只要比较这两个值与 的距离，较小者就是当前前缀的最优贡献。

四、Python 为什么用树状数组

C++ 可以直接用 multiset，Java 可以用 TreeMap。

Python 没有现成的平衡树，直接用列表插入会退化成 。这里更稳的做法是：

1. 先把所有 离散化；
2. 用树状数组维护每个值当前出现了几次；
3. 通过前缀个数和第 小查询，找出前驱和后继对应的真实值。

这样每次插入和查询都是 。

五、复杂度分析

• 计算所有 、：
• 从右到左做插入与查询：

总时间复杂度：

空间复杂度：

参考代码

• Python

import sys
from bisect import bisect_left

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


class Fenwick:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, idx, val):
        while idx <= self.n:
            self.bit[idx] += val
            idx += idx & -idx

    def sum(self, idx):
        res = 0
        while idx > 0:
            res += self.bit[idx]
            idx -= idx & -idx
        return res

    def kth(self, k):
        idx = 0
        step = 1 << (self.n.bit_length() - 1)
        while step:
            nxt = idx + step
            if nxt <= self.n and self.bit[nxt] < k:
                idx = nxt
                k -= self.bit[nxt]
            step >>= 1
        return idx + 1


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

    f = [0] * (n + 1)
    g = [0] * (n + 2)

    pref_max = 0
    pref_sum = 0
    for i, x in enumerate(a, 1):
        pref_max = max(pref_max, x)
        pref_sum += x
        f[i] = pref_max * i - pref_sum

    suf_max = 0
    suf_sum = 0
    for i in range(n, 0, -1):
        x = a[i - 1]
        suf_max = max(suf_max, x)
        suf_sum += x
        g[i] = suf_max * (n - i + 1) - suf_sum

    vals = sorted(set(g[2 : n + 1]))
    fw = Fenwick(len(vals))

    ans = 0
    total = 0

    for i in range(n - 1, 0, -1):
        pos = bisect_left(vals, g[i + 1]) + 1
        fw.add(pos, 1)
        total += 1

        x = f[i]
        idx = bisect_left(vals, x)
        left_cnt = fw.sum(idx)

        best = 10**30

        if left_cnt > 0:
            pre = vals[fw.kth(left_cnt) - 1]
            best = min(best, abs(x - pre))

        if left_cnt < total:
            nxt = vals[fw.kth(left_cnt + 1) - 1]
            best = min(best, abs(x - nxt))

        ans += best

    print(ans)


if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int64> a(n + 1), f(n + 1), g(n + 2);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    int64 pref_max = 0, pref_sum = 0;
    for (int i = 1; i <= n; ++i) {
        pref_max = max(pref_max, a[i]);
        pref_sum += a[i];
        f[i] = pref_max * i - pref_sum;
    }

    int64 suf_max = 0, suf_sum = 0;
    for (int i = n; i >= 1; --i) {
        suf_max = max(suf_max, a[i]);
        suf_sum += a[i];
        g[i] = suf_max * (n - i + 1LL) - suf_sum;
    }

    multiset<int64> st;
    int64 ans = 0;

    for (int i = n - 1; i >= 1; --i) {
        st.insert(g[i + 1]);

        int64 x = f[i];
        auto it = st.lower_bound(x);
        int64 best = (1LL << 62);

        if (it != st.end()) {
            best = min(best, llabs(*it - x));
        }
        if (it != st.begin()) {
            --it;
            best = min(best, llabs(*it - x));
        }

        ans += best;
    }

    cout << ans << '\n';
    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buf = new byte[1 << 16];
        private int ptr = 0;
        private int len = 0;

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
                if (len <= 0) {
                    return -1;
                }
            }
            return buf[ptr++];
        }