【Tyvj1063】数字串

描述 Description

给你一个长度为 n 的数字串,数字串里会包含 1-m 这些数字。如果连续的一段数字子串包含了 1-m 这些数字,则称这个数字字串为 NUM 串。你的任务是求出长度最短的 NUM 串是什么,只需要输出这个长度即可。

1<=n,m<=200000

输入格式 InputFormat

第一行给定 n 和 m。
第二行 n 个数,表示数字串,数字间用空格隔开。

输出格式 OutputFormat

如果存在 NUM 串则输出最短 NUM 串长度,否则输出 “NO”。

样例输入 SampleInput

5 3
1 2 2 3 1

样例输出 SampleOutput

3


Tyvj 1063


代码 Code

队列什么的这题通过率真是不科学。。。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define inf 0x7fffffff
int a[300000];
int b[300000];
int i,j,t,n,m,l,r,k,z,y,x;
int main()
{
    scanf("%d%d",&n,&m);
    memset(b,0,sizeof(b));
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    l=1;z=inf;t=1;b[a[l]]=1;
    for (r=2;r<=n;r++)
    {
        if (t==m) z=min(z,r-l);
        if (b[a[r]]==0) t++;
        b[a[r]]++;
        while (b[a[l]]>1)
        {
            b[a[l]]--;
            l++;
        }
    }
    if (t==m) z=min(z,n-l+1);
    if (z==inf) printf("NO\n");
    else printf("%d\n",z);
    return 0;
}