题意分析

Farmer John 的 N 头奶牛（1 ≤ N ≤ 100,000）排成一排。每头奶牛的品种用一个范围在 1 到 K（1 ≤ K ≤ 10,000）之间的数字表示。Farmer John 很好奇，他能否用 1 到 K 范围内的数字构造一个尽可能短的序列，而这个序列不是奶牛品种 ID 序列的子序列。请帮助他解决这个问题。

输入格式：

• 第 1 行：两个整数 N 和 K。
• 第 2 到 N+1 行：每行包含一个整数，表示一头奶牛的品种 ID。

输出格式：

• 第 1 行：最短的、不是输入序列子序列的序列的长度。

解题思路

关键观察：

• 如果给定的序列中包含了所有可能的长度为 L 的序列（即 1 到 K 的所有排列组合），那么最短的不在序列中的子序列的长度就是 L+1。
• 反之，如果序列中不包含所有可能的长度为 L 的序列，那么最短的不在序列中的子序列的长度就是 L。

算法选择：

• 遍历序列，统计当前序列中包含的完整长度为 L 的序列的数量。
• 如果在遍历过程中，能够收集到所有 K 种数字，则说明可以形成一个长度为 L+1 的序列。
• 最终，最短的不在序列中的子序列的长度就是统计的完整序列数量加 1。

代码实现

#include <stdio.h>
#include <string.h>

#define clr(x) memset(x, 0, sizeof(x))

int v[10005];

int main() {
    int n, k, p, i, res, num;
    while (scanf("%d%d", &n, &k) != EOF) {
        res = num = 0;
        clr(v);
        for (i = 0; i < n; i++) {
            scanf("%d", &p);
            if (!v[p]) {
                v[p] = 1;
                num++;
                if (num == k) {
                    res++;
                    clr(v);
                    num = 0;
                }
            }
        }
        printf("%d\n", res + 1);
    }
    return 0;
}