题解：B4098 [CSP-X2022 山东] 动物园

Yxa_Sheep · 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;
}

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

题目传送门