滴滴笔试滴滴笔试题 0317

笔试时间：2024年03月17日

历史笔试传送门：2023秋招笔试合集

第一题

题目

小明正在模拟陨石对地质的危害。在小明的模型下，将地面从0,1,2…直到N依次从左到右进行标号。每次陨石i坠落，会使得标号在[L,R]这个区间范围内的地面受到一次陨石打击。在 M 次陨石坠落后，小明想知道某些指定地面在刚才 M 次陨石坠落中受到了多少次陨石打击。

输入描述

第一行两个正整数 N,M，含义如题面；

接下来一行 M 个数，分别为L1,L2,...,Ln表示这M次陨石打击的左边界。

接下来一行 M 个数，分别为R1,R2,...,Rn，表示这M次陨石打击的右边界。

接下来一个数 Q，表示小明询同次数。

接下来一行Q个数x，表示小明想知道标号为x的地面在刚才M次阳石坠落中受到了多少次打击。

输出描述

输出一行 Q 个数，用空格隔开(无行未空格)，分别表示每次询问的答案。

样例输入

4 3

1 2 2

2 3 4

5

0 1 2 3 4

样例输出

0 1 2 3 4

参考题解

使用差分数组处理区间更新问题，然后根据查询输出每个点的最终值；

C++：[此代码未进行大量数据的测试，仅供参考]

   void solve() {
        int n, m;
        cin >> n >> m;
        n++;
        
        vector<pair<int, int>> intervals(m);
        for(int i = 0;i < m;i++) {
            int l;
            cin >> l;
            intervals[i].first = l;
        }
        for(int i = 0;i < m;i++) {
            int r;
            cin >> r;
            intervals[i].second = r;
        }
        
        vector<int> diff(n);
        for(int i = 0;i < m;i++) {
            int l = intervals[i].first, r = intervals[i].second;
            diff[l]++;
            if(r + 1 < n) {
                diff[r + 1]--;
            }
        }
        
        vector<int> ans(n);
        int cur = 0;
        for(int i = 0;i < n;i++) {
            cur += diff[i];
            ans[i] = cur;
        }
        
        int q;
        cin >> q;
        for(int i = 0;i < q;i++) {
            int idx;
            cin >> idx;
            cout << ans[idx] << " ";
        }
        cout << "\n";
    }

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Solution {
    public static void solve() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        n++;
        
        List<Pair<Integer, Integer>> intervals = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int l = scanner.nextInt();
            intervals.add(new Pair<>(l, 0));
        }
        for (int i = 0; i < m; i++) {
            int r = scanner.nextInt();
            intervals.get(i).setValue(r);
        }
        
        int[] diff = new int[n];
        for (int i = 0; i < m; i++) {
            int l = intervals.get(i).getKey();
            int r = intervals.get(i).getValue();
            diff[l]++;
            if (r + 1 < n) {
                diff[r + 1]--;
            }
        }
        
        int[] ans = new int[n];
        int cur = 0;
        for (int i = 0; i < n; i++) {
            cur += diff[i];
            ans[i] = cur;
        }
        
        int q = scanner.nextInt();
        for (int i = 0; i < q; i++) {
            int idx = scanner.nextInt();
            System.out.print(ans[idx] + " ");
        }
        System.out.println();
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

def solve():
    n, m = map(int, input().split())
    n += 1

    intervals = []
    for _ in range(m):
        l = int(input())
        intervals.append((l, 0))
    for i in range(m):
        r = int(input())
        intervals[i] = (intervals[i][0], r)

    diff = [0] * n
    for l, r in intervals:
        diff[l] += 1
        if r + 1 < n:
            diff[r + 1] -= 1

    ans = [0] * n
    cur = 0
    for i in range(n):
        cur += diff[i]
        ans[i] = cur

    q = int(input())
    for _ in range(q):
        idx = int(input())
        print(ans[idx], end=" ")
    print()

第二题

题目

小A所在的企业中，每个员工在请求授权的时候都需要向他上面的某一级领导提出申请。为了避免混乱，一个员工只会向他的上级领导中技术能力与他最相近的那位领导提出申请。现在小A想知道每个人的申请对象是谁。小A所在企业的组织架构可以用一棵有根树来描述。即除了树根对应的最高领导以外，每个人都有唯一的一个直屋领导。同时，每个员工的技术能力均可以用一个正整数表示，称为技术等级。两个人之间的技术能力越近则他们的技术等级之差的绝对值越小。