✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

滴滴-2026.03.15

1. 小基 的分段巡检计划

问题描述

小基 正在整理一条连续巡检线路。

整条线路一共有 个观测点，按顺序编号为 到 。第 个观测点记录了一个标签值 。

现在需要把整条线路划分成恰好 段连续巡检片段，每一段都至少包含一个观测点。

对于某一段片段 ，定义它的完整度为 ，也就是这段片段中没有出现过的最小非负整数。

例如：

• 。
• 。
• 。

设这 段片段分别为 ，则本次划分的评分定义为：

现在希望通过选择合适的划分方式，让这个评分 尽可能大。请输出能够达到的最大值。

输入格式

第一行输入两个整数 ，分别表示观测点数量和需要划分出的连续片段数量。

第二行输入 个整数 ，表示每个观测点记录的标签值。

输出格式

输出一个整数，表示最大可能的评分 。

样例输入

6 2
0 0 1 1 2 2

样例输出

1

数据范围

样例	解释说明
样例 1	若划分成 和 ，两段的 分别为 和 ，最小值只有 。若划分成 和 ，最小值仍然不理想。最优做法之一是划分成 和 ，或者其他等价方案，使得两段的最小 恰好能达到 ，而想让答案达到 时，每一段都必须同时包含 和 ，显然无法做到，因此答案是 。

题解

这题表面上是在讨论怎么分段，真正卡人的地方其实只有一句话：

如果想让某一段的 ，那么这段里必须同时出现 。

因为 是“没出现过的最小非负整数”，所以只要前面的数缺了一个， 就不可能到达 。

于是整题可以换个问法：

能不能把原数组划成至少 段，并且每一段都包含 这 个数？

如果某个 可以做到，那么更小的值一定也能做到；如果某个 做不到，更大的值自然更不可能做到。这个单调性一出来，答案就可以二分了。

一、固定答案 怎么判定

先假设已经知道目标值是 。

此时只需要从左到右扫一遍数组，尽量多切出合法片段。

当前片段里只关心两类信息：

1. 小于 的数里，已经收集到了哪些。
2. 还差多少个不同的值，才能把 到 全部凑齐。

扫描时：

• 如果当前数 ，它对“是否凑齐 ”没有直接帮助，可以略过。
• 如果 ，并且它在当前片段中还是第一次出现，就把它计入当前片段。
• 一旦当前片段已经把 全部凑齐，就立刻切一段。

为什么可以立刻切？

因为目标是“尽量切出更多合法片段”。当前这段既然已经满足要求，再继续往右扩展，只会把元素浪费在这一段里，不会帮助后面多切出合法段数。所以“越早切越好”。

这就变成了一个很直接的贪心判定。

二、为什么二分答案成立

设 check(x) 表示“是否能切出至少 个合法片段，使每段的 ”。

如果 check(x) 为真，那么对任意 ：

• 每段既然已经包含了 ，
• 那当然也包含 ，
• 所以 check(y) 也一定为真。

这说明可行性关于 是单调的，因此可以二分最大的可行值。

三、实现细节

判定时不能每切一段就把“出现数组”整段清空一遍，不然会多出很多重复开销。

更顺手的写法是用时间戳数组：

• vis[v] 记录值 上一次是在第几段里被标记过。
• 当前片段编号记作 tag。
• 如果 vis[v] != tag，说明值 还没在当前片段出现过。

这样每次切段时只需要 tag += 1，不用真的去清空数组。

四、复杂度分析

设二分检查的目标值为 。

• 一次 check(x) 只需要线性扫描一遍数组，时间复杂度是 。
• 二分答案的范围可以取到 ，总共需要 次判定。

所以总时间复杂度是 ，空间复杂度是 。

在 的范围内完全可以通过。

参考代码

• Python

import sys

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


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

    def check(x: int) -> bool:
        # MEX >= 0 永远成立。
        if x == 0:
            return True

        vis = [0] * x
        tag = 1
        got = 0
        seg = 0

        for v in arr:
            # 只有 0..x-1 这些值会影响当前判定。
            if v < x and vis[v] != tag:
                vis[v] = tag
                got += 1

                # 当前片段已经凑齐 0..x-1，可以立刻切段。
                if got == x:
                    seg += 1
                    if seg >= k:
                        return True
                    tag += 1
                    got = 0

        return False

    lo, hi = 0, n // k
    ans = 0

    while lo <= hi:
        mid = (lo + hi) // 2
        if check(mid):
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1

    print(ans)


if __name__ == "__main__":
    solve()

• Cpp

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

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

    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    auto check = [&](int x) -> bool {
        // MEX >= 0 始终成立。
        if (x == 0) return true;

        vector<int> vis(x, 0);
        int tag = 1;
        int got = 0;
        int seg = 0;

        for (int v : a) {
            // 只关心 0..x-1 是否都出现过。
            if (v < x && vis[v] != tag) {
                vis[v] = tag;
                ++got;

                // 当前片段第一次凑齐全部目标值，立即切段。
                if (got == x) {
                    ++seg;
                    if (seg >= k) return true;
                    ++tag;
                    got = 0;
                }
            }
        }

        return false;
    };

    int lo = 0, hi = n / k, ans = 0;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (check(mid)) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    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, len = 0;

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

        int nextInt() throws IOException {
            int c;
            while ((c = read()) <= ' ') {
                if (c == -1) return -1;
            }
            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }
            int val = 0;
            while (c > ' ') {
                val = val * 10 + c - '0';
                c = read();
            }
            return val * sign;
        }
    }

    static int n, k;
    static int[] arr;

    static boolean check(int x) {
        // MEX >= 0 永远成立。
        if (x == 0) return true;

        int[] vis = ne