滴滴笔试 滴滴笔试题 20260315滴滴笔试真题解析

笔试时间：2026年3月15日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：划分（MEX 最小值最大化）

难度： 中等

题目描述

给定一个长度为 的数组 和一个整数 。需要将整个数组划分成恰好 个连续子数组，每个子数组至少包含一个元素。

对一个数组 ， 表示没有出现在其中的最小非负整数。在所有可能的划分中，定义：

其中 为划分得到的子数组。你的任务是使 尽量大，并求出能达到的最大值。

MEX 定义： 指在数组中没有出现过的最小非负整数。示例：

输入描述

第一行包含两个整数 （），表示数组长度和要划分的子数组个数；第二行包含 个整数 （），表示数组的元素。

输出描述

输出一行，一个整数，表示在某种将数组划分成 个子数组的方式下，最大可能值 。

样例输入

6 2
0 0 1 1 2 2

样例输出

1

参考题解

解题思路：

首先注意到所求的这个 是满足单调性的，也就是大的 能达到，那么更小的一定能达到，那么考虑二分答案。对于给定的 ，通过贪心验证是否能将数组划分为 个连续子数组，且每个子数组的 MEX 都 。具体做法是从左往右遍历数组，用 set 来维护当前的 mex，如果当前 mex 了就划分一次，最后看能不能划分出 个子数组。

C++：

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

vector<int> a;
int n, k;

bool check(int mid) {
    if (!mid) return true;
    set<int> s;
    int cnt = 0;
    for (int x : a) {
        if (x < mid) s.insert(x);
        if (s.size() == mid) cnt++, s.clear();
    }
    return cnt >= k;
}

int main() {
    cin >> n >> k;
    a.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int l = 0, r = n, ans = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    cout << ans;
}

Java：

import java.util.*;

public class Main {
    static int[] a;
    static int n, k;

    static boolean check(int mid) {
        if (mid == 0) return true;
        Set<Integer> s = new HashSet<>();
        int cnt = 0;
        for (int x : a) {
            if (x < mid) s.add(x);
            if (s.size() == mid) {
                cnt++;
                s.clear();
            }
        }
        return cnt >= k;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        int l = 0, r = n, ans = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(mid)) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        System.out.println(ans);
    }
}

Python：

import sys
input = sys.stdin.readline

def check(mid, a, k):
    if mid == 0:
        return True
    s = set()
    cnt = 0
    for x in a:
        if x < mid:
            s.add(x)
        if len(s) == mid:
            cnt += 1
            s.clear()
    return cnt >= k

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    l, r, ans = 0, n, 0