✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

滴滴-2026.03.08

这套滴滴题是很典型的“两道题都要先把问题压扁”的组合。

第一题表面上是在问很多个阈值下的统计结果，真正该抓的是“最终到底出现了哪些正高度”；第二题表面上是三元组计数，真正该做的是固定前两个量后一次算完第三个量的贡献。

题目 1：仓储层位观测

这题的关键不在于把每个 都算出来，而在于意识到答案只和“出现过多少种正高度”有关。

一旦把这一点想清楚，后面就是标准的区间加离散化：把所有会改变高度的端点抠出来，再在压缩后的坐标上做差分。

题目 2：三路投放方案统计

真正的突破口是把三层枚举降成两层。固定 之后， 的可选范围可以直接由两个上界取最小值。

难点主要在复杂度判断。看到 的上界大约是 以后，就知道总枚举次数是一段调和级数，这题就落回了可做范围。

1. 仓储层位观测

问题描述

K 小姐在整理一条很长的仓储通道。通道里一共有 个货位，编号为 到 。一开始，每个货位上都没有箱子。

接下来会有 批补货。第 批补货会把 个相同的箱子，同时加到编号位于 的每一个货位上。于是，所有补货结束后，每个货位都会得到一个最终高度。

现在定义函数 表示：最终高度 大于等于 的货位有多少个。

K 小姐不关心 的具体变化过程，她只想知道：当 从 一直取到很大的值时， 一共会出现多少种不同的取值。

输入格式

第一行输入两个整数 和 ，分别表示货位数量与补货批次数。

接下来有 行，每行输入三个整数 、、，表示这一批补货会让区间 中的每个货位高度增加 。

输出格式

输出一个整数，表示 这一长串数值里，不同取值的总个数。

样例输入

10 4
7 8 5
5 7 5
1 2 1
3 5 3

样例输出

6

数据范围

• 。

• 。

• 。

• 。

样例	解释说明
样例 1	最终高度依次为 。正高度只有 这 种，所以 会出现 种不同取值，最后那个 来自所有货位都不够高时的 。

题解

真正麻烦的地方，不是去算某一个固定的 ，而是要看它一共会变化出多少个不同答案。

先盯住“什么时候会变”。假设某个货位的最终高度是 ，那么当阈值 从小到大增加时，这个货位会在 的那一刻从统计里消失。在别的位置，它对 没影响。于是， 只会在“跨过某个真实出现过的正高度”时发生变化。

这就得到一个非常关键的结论：答案其实等于“最终所有货位里，正高度有多少种不同取值”再加上 。多出来的这个 ，对应的是阈值继续升高后，所有货位都被删空，此时 。

所以题目被改写成：想办法找出所有 出现过的不同正高度。

问题又来了， 最大能到 ，显然不可能真的把每个货位都算出来。这里要利用区间加的结构：所有变化只会发生在每次补货的左端点 ，以及右端点后一位 。把这些位置和边界 全部收集起来、排序去重后，相邻两个坐标之间的整段货位，最终高度一定相同。这样一来，本来可能有 个位置，现在只剩下不超过 个关键分界点。

接着在压缩后的坐标上做差分。对一条操作 加上 ，只需要在 对应的位置加上 ，在 对应的位置减去 。最后扫一遍前缀和，就能得到每个压缩段的真实高度。

扫的过程中，不需要记录整段有多长，因为题目只问“出现过哪些高度”，而不是每个高度出现了多少次。只要某一段的高度大于 ，就把这个高度丢进集合里。集合大小记为 ，最终答案就是 。

为什么这样做一定正确？原因分两步：

第一，坐标压缩不会丢信息。因为任意两个相邻关键点之间，再也没有操作端点穿过，所以这一整段货位经历的所有补货完全一样，最终高度当然也完全一样。

第二，答案和不同正高度的个数一一对应。若正高度从小到大是 ，那么当阈值依次跨过 时，至少会有一批货位退出统计， 会严格下降；而在两个相邻高度之间，满足“高度至少为 ”的货位集合并不会变化。因此， 的不同取值正好是这 次下降形成的 个值，再加上最后的 ，总数就是 。

复杂度方面，坐标数不超过 。排序和每次二分定位的总复杂度是 ，扫前缀和是 ，空间复杂度也是 。在 的范围内完全可以通过。

参考代码

• Python

import sys
from bisect import bisect_left

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


def main():
    n, m = map(int, input().split())

    # 收集所有会改变高度的关键位置。
    pos = [1, n + 1]
    ops = []
    for _ in range(m):
        l, r, d = map(int, input().split())
        rp = r + 1
        ops.append((l, rp, d))
        pos.append(l)
        pos.append(rp)

    # 坐标压缩后，相邻关键点之间的整段高度相同。
    pos = sorted(set(pos))
    dif = [0] * (len(pos) + 1)

    def idx(val):
        # 找到原坐标在压缩数组中的位置。
        return bisect_left(pos, val)

    for l, rp, d in ops:
        dif[idx(l)] += d
        dif[idx(rp)] -= d

    cur = 0
    seen = set()
    for i in range(len(pos) - 1):
        # 前缀和就是当前压缩段的真实高度。
        cur += dif[i]
        if cur > 0:
            # 只关心“出现过哪些正高度”，长度无关紧要。
            seen.add(cur)

    # 多出来的 1，对应阈值足够大时的 f(x)=0。
    print(len(seen) + 1)


if __name__ == "__main__":
    main()

• Cpp

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

using ll = long long;

int get_id(const vector<ll>& pos, ll val) {
    return lower_bound(pos.begin(), pos.end(), val) - pos.begin();
}

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

    ll n;
    int m;
    cin >> n >> m;

    vector<ll> pos;
    pos.reserve(m * 2 + 2);
    pos.push_back(1);
    pos.push_back(n + 1);

    vector<array<ll, 3>> ops;
    ops.reserve(m);

    for (int i = 0; i < m; ++i) {
        ll l, r, d;
        cin >> l >> r >> d;
        ll rp = r + 1;
        ops.push_back({l, rp, d});
        pos.push_back(l);
        pos.push_back(rp);
    }

    // 压缩所有关键坐标，减少需要真正扫描的位置数。
    sort(pos.begin(), pos.end());
    pos.erase(unique(pos.begin(), pos.end()), pos.end());

    // dif 记录压缩坐标上的差分变化量。
    vector<ll> dif(pos.size() + 1, 0);
    for (const auto& op : ops) {
        int l_id = get_id(pos, op[0]);
        int r_id = get_id(pos, op[1]);
        dif[l_id] += op[2];
        dif[r_id] -= op[2];
    }

    ll cur = 0;
    set<ll> seen;
    for (size_t i = 0; i + 1 < pos.size(); ++i) {
        // 每个压缩段里的所有货位，高度完全一致。
        cur += dif[i];
        if (cur > 0) {
            seen.insert(cur);
        }
    }

    // 不同正高度个数 + 1，就是答案。
    cout << static_cast<ll>(seen.size()) + 1 << '\n';
    return 0;
}

• Java

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.Arrays;
import java.util.TreeSet;

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

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

        long nextLong() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ');

            lo