The Cow Lineup

题号 NC106586
名称 The Cow Lineup

题目描述

给定一个长度为n的序列A，和数值范围k，找到一个最短的在A中不存在的子序列，并输出长度

样例

输入
14 5
1
5
3
2
5
1
3
4
4
2
5
1
2
3
输出
3

原序列：[1 5 3 2 5 1 3 4 4 2 5 1 2 3] ,其中长度为1的所有可能的子序列[1,2,3,4,5]在原序列中都能找到,
长度为2的所有可能的子序列
[11,12,13,14,15,
21,22,23,24,25,
31,32,33,34,35,
41,42,43,44,45,
51,52,53,54,55]
在原序列中都能找到
而长度为3的所有可能子序列中224在原序列中找到不到所以答案为3

算法

(思维)

假设长度为k的所有可能子序列在原序列中都能找到，那么长度为k - 1的所有可能子序列在原序列中也都能找到，所以我们可以枚举子序列的长度，如果说长度为所有长度为k-1的子序列，在原序列的[1,l1]区间内就可对找到(其中l1为最小的一个左边界，因为如果[1,l1]中能找到所有长度为k-1的子序列，那么[1,l1 + 1]也一定能找到)那么在区间[l1 + 1,n]中一定要包含[1 ~ k]中的所有数才能找找到所有长度为k的子序列，同理在[l1 + 1,n]中找到一个最小的l2,保证在原序列的[1,l2]区间内就可对找到所有长度为k的子序列，重复上述操作,直到在某个[li + 1,n]的区间中找不到[1 ~ k]的某个数为止，那么当前枚举的长度就是答案。

时间复杂度O（N）

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
// #include <unordered_map>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <cmath>

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
const int N = 100010;
int a[N];
int st[N];
int n,k;

void solve()
{
    scanf("%d%d",&n,&k);
    for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);

    for(int i = 1,j = 1;;i ++)
    {
        int cnt = 0;
        while(j <= n && cnt < k)
        {
            if(st[a[j]] < i) 
            {
                cnt ++;
                st[a[j]] ++;
            }
            j ++;
        }
        if(cnt != k)
        {
            printf("%d\n",i);
            return;
        }
    }
}

int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #else
    #endif // LOCAL
    int T = 1;
    // init();
    // scanf("%d",&T);
    while(T --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}