滴滴笔试 滴滴笔试题 20260308

笔试时间：2026年03月08日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：方格世界

难度：中等

涉及知识点： 差分数组与扫描线算法

题目描述

方格世界中所有方格的长宽高均为 1 米。方格世界中有 n 个方格堆，编号依次为 1~n。每个方格堆中的方格都是按照从下到上的方式堆成一列（假设有 k 个方格，则这 k 个方格堆成了一个长宽均为 1 米，高为 k 米的长方体）。初始时每个方格堆中的方格数量均为 0。方格世界会下 m 场"方格雨"，第 i 场"方格雨"会使得编号在 l_i 到 r_i 之间的方格堆的方格数量增加 d_i。定义 f(h) 表示经过"方格雨"后方格世界中高度大于等于 h 米的方格堆个数。你需要计算 f(h) 中一共有多少不同的取值。

输入描述

输入第一行有两个整数 n（1 ≤ n ≤ 10^9）和 m（1 ≤ m ≤ 10^5），分别表示方格世界中方格堆的个数、"方格雨"的次数。接下来 m 行中，第 i 行有三个整数 l_i, r_i（1 ≤ l_i ≤ r_i ≤ n）和 d_i（1 ≤ d_i ≤ 10^4），分别表示"方格雨"作用的方格堆范围和增加的方格数量。

输出描述

输出一个整数，表示 f(h) 中一共有多少不同的取值。

样例

输入：

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

输出：

6 

说明：

第一场"方格雨"后各个方格堆中方格数量: [0 0 0 0 0 0 5 5 0 0]；第二场"方格雨"后各个方格堆中方格数量: [0 0 0 0 5 5 10 5 0 0]；第三场"方格雨"后各个方格堆中方格数量: [1 1 0 0 5 5 10 5 0 0]；第四场"方格雨"后各个方格堆中方格数量: [1 1 3 3 8 5 10 5 0 0]。

依次计算 f(0)=10, f(1)=8, f(2)=6, f(3)=6, f(4)=4, f(5)=4, f(6)=3, f(7)=3, f(8)=3, f(9)=1, f(10)=1, f(11)=0。

f(h) 中一共有 6 个不同的取值。

参考题解

解题思路：

由于 f(h) 的值仅在 h 超过某个方格堆的高度时才发生变化，题目本质是求所有方格堆中出现了多少种不同的高度值。随着 h 变大，f(h) 会不断减小。只有当 h 恰好超过某一个方格堆的实际高度时，f(h) 的值才会发生变化。因此 f(h) 的不同取值个数 = 方格世界中出现的不同高度（大于0的高度）的种类数 + 1（高度为0的情况）。

我们利用差分思想将"方格雨"转化为坐标轴上的高度增减事件，按位置排序后通过扫描线累加得出各区间的高度，并用 Set 统计所有出现的不同正高度种类数，最后加 1（即高度为 0 的情况）即为答案。

Java：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        if (!scan.hasNextInt()) {
            return;
        }
        int limit = scan.nextInt();
        int opCount = scan.nextInt();

        Item[] items = new Item[opCount * 2];
        int index = 0;
        for (int j = 0; j < opCount; j++) {
            int start = scan.nextInt();
            int end = scan.nextInt();
            long diff = scan.nextLong();
            items[index++] = new Item(start, diff);
            items[index++] = new Item(end + 1, -diff);
        }

        Arrays.sort(items);

        long currentVal = 0;
        int lastPos = -1;
        Set<Long> resSet = new HashSet<>();
        for (int j = 0; j < items.length; j++) {
            Item it = items[j];
            if (lastPos != -1 && it.loc > lastPos) {
                if (currentVal > 0) {
                    resSet.add(currentVal);
                }
            }
            currentVal += it.delta;
            lastPos = it.loc;
        }
        System.out.println(resSet.size() + 1);
    }

    static class Item implements Comparable<Item> {
        int loc;
        long delta;

        public Item(int loc, long delta) {
            this.loc = loc;
            this.delta = delta;
        }

        @Override
        public int compareTo(Item target) {
            return Integer.compare(this.loc, target.loc);
        }
    }
}

C++：

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

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

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<pair<int, long long>> events;
    events.reserve(m * 2);

    for (int j = 0; j < m; j++) {
        int start, end;
        long long diff;
        cin >> start >> end >> diff;
        events.push_back({start, diff});
        events.push_back({end + 1, -diff});
    }

    sort(events.begin(), events.end());

    long long currentVal = 0;
    int lastPos = -1;
    set<long long> resSet;

    for (auto& [loc, delta] : events) {
        if (lastPos != -1 && loc > lastPos) {
            if (currentVal > 0) {
                resSet.insert(currentVal);
            }
        }
        currentVal += delta;
        lastPos = loc;
    }

    cout << resSet.size() + 1 << endl;
    return 0;
}

Python：

import sys
from collections import defaultdict

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    n = int(input_data[idx]); idx += 1
    m = int(input_data[idx]); idx += 1

    events = []
    for _ in range(m):
        start = int(input_data[idx]); idx += 1
        end = int(input_data[idx]); idx += 1
        diff = int(input_data[idx]); idx += 1
        events.append((start, diff))
        events.append((end + 1, -diff))

    events.sort()

    current_val = 0
    last_pos = -1
    res_set = set()

    for loc, delta in events:
        if last_pos != -1 and loc > last_pos:
            if current_val > 0:
                res_set.add(current_val)
        current_val += delta
        last_pos = loc

    print(len(res_set) + 1)

if __name__ == "__main_