自动搬运

查看原文

来自洛谷，原作者为

	Yxa_Sheep 打表过样例，暴力出奇迹，搜索真牛逼，骗分进省一||深搜 MLE，广搜 TLE，打表 RE，退火又 CE||删掉 display 看主页||被封取关（解封后私信）||六年级蒟蒻 ，代词请用“他”||当前状态：<离线>

搬运于2025-08-24 21:17:05，当前版本为作者最后更新于2025-06-19 17:09:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

题意

选出一个区间，使这个区间包含 $1$ 到 $m$ 之间的所有数，求这个区间最短长度是多少。

思路

用 $l$ 与 $r$ 两个指针，表示区间的左端点与区间的右端点。如果这个区间包含了 $1$ 到 $m$ 之间的所有数，更新 $ans$ 的值，否则继续扩大这个区间。细节看代码。

代码

有注释

#include <bits/stdc++.h>
using namespace std;
int n, m, l = 1, r, x, ans = 1e6, a[1000010], book[2010]; // l要初始为 1，ans 开 1e6 是因为 n 最大为 1e6，ans <= n
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
	//毫无技巧的输入
    while (r <= n) //右端点在 n 以内
    {
        if (x == m) //包含 1 ~ m 所有数
        {
            ans = min(ans, r - l + 1); //更新ans
            if (!--book[a[l++]]) //左端点加一
                x--; /*如果左端点的那个数去掉后没有和它一样的数了
					则出现的不同数字的数量减一*/
        }
        else
            if (!book[a[++r]]++) //右端点加一
                x++; /*如果右端点的那个数没出现过
					则出现的不同数字的数量加一*/
    }
    printf("%d", ans * 10);
    return 0;
}

无注释

#include <bits/stdc++.h>
using namespace std;
int n, m, l = 1, r, x, ans = 1e6, a[1000010], book[2010];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    while (r <= n)
    {
        if (x == m)
        {
            ans = min(ans, r - l + 1);
            if (!--book[a[l++]])
                x--;
        }
        else
            if (!book[a[++r]]++)
                x++;
    }
    printf("%d", ans * 10);
    return 0;
}

个人觉得代码加注释看起来很长。题解来之不易，且看且珍惜。给个赞再走吧。

题目传送门