题解-P5093

· · 题解

简要分析

我的思路与 da32s1da 大佬的大致相同，这篇题解是来解释一下这个思路的正确性的

我们将 k 个数字均出现的一段最短连续序列分为一组，答案就是组数个数再加一。

但是为什么呢？

很显然在每一组中的每一个数字出现次数大于等于一次，因此我们肯定能得到长度小于等于组数的全排列

假如分完组后没有数字剩余，那么答案显然就是组数加一

当有数字剩余时，即使我们能得到一些长度为组数加一的子序列，但是肯定不能得到全部，如果实在还是无法理解的读者请看一下下面这个例子

1 2 3 4 5 1 2 3 4 5 1 2 3 4

上面这个序列我们可以得到大部分的长度为 3 的序列，但是三个 5 组成的序列我们很明显无法得到

对于这个思路还有疑问的读者可以再手模几组数据来理解

完整代码

#include <bits/stdc++.h>
using namespace std;
int i, n, a, x, t = 0, cnt = 1, v[105][10005] = {0};
int main() {
    scanf("%d%d", &n, &k);
    for (i = 1; i <= n; i++) {
        scanf("%d", &a);
        if (!v[cnt][a]) v[cnt][a] = 1, t++; //统计这一组中数字的数量
        if (k == t) cnt++, t = 0;   //数字全有了组数就加一
    }
    printf("%d", cnt);
    return 0;
}