首页 > 代码库 > 【Luogu1638】逛画展

【Luogu1638】逛画展

点此进入原题

算法(有技巧的)模拟

题解

这题可以不用真实的队列,只要用两个变量模拟一下就可以啦

也可以说是枚举的思想:这题很容易想到O(n^2)的枚举区间的算法,容易TLE。先找到第一个包含所有不同数字的区间[i,j],然后让i+1,同时枚举j找到另一个区间,然后取j-i的最小值就OK辣。判断不同的数字完全可以用桶解决

可能我的语文差了一点,具体看我的代码吧(好难表述啊QAQ)

代码

#include<cstdio>
const int N=1000005,M=2017;
int a[N],b[M],n,m,l,r=1<<30;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1,j=0,k=0;i<=n;i++) //枚举区间[i,j]
    {
        while(k<m) //枚举j找到包含m个不同元素的区间[i,j].(k表示不同的数的个数)
        {
            j++; //小细节:j初值为0,提前自增,避免了一些麻烦
            if(j>n) break;
            if(b[a[j]]==0) k++; //此数未出现过,k++
            b[a[j]]++;
        }
        if(k==m&&r-l>j-i) l=i,r=j; //修改最小值
        b[a[i]]--; //i+1前将第i个数移出区间
        if(b[a[i]]==0) k--; //如果此数在[i,j]中只出现一次并且现在被移出,那么k--
    }
    printf("%d %d",l,r); //最后输出答案区间,结束~
}

 

【Luogu1638】逛画展