逛画展

题意

给出一列画作，第 i 幅画由编号 a_i 的画家创作，所有画家编号在 1..m 之间。

要求找一个最短的连续区间 [x, y]，使得这个区间里包含了：

所有 1..m 号画家的作品至少各一幅

如果有多组最短区间，输出左端点 x 最小的那组。

思路

先看一个最直接的小数据暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int ans_l = 1;
    int ans_r = n;

    // 朴素枚举所有区间，检查是否覆盖了所有画家。
    for (int l = 1; l <= n; l++) {
        vector<int> cnt(m + 1, 0);
        int kind = 0;
        for (int r = l; r <= n; r++) {
            if (cnt[a[r]] == 0) {
                kind++;
            }
            cnt[a[r]]++;

            if (kind == m) {
                if (r - l < ans_r - ans_l) {
                    ans_l = l;
                    ans_r = r;
                }
                break;
            }
        }
    }

    cout << ans_l << ' ' << ans_r << '\n';
    return 0;
}

brute.cpp 枚举左端点 l，再向右扩展找到第一个能覆盖所有画家的右端点 r，用它更新答案。

这个思路很自然，但如果对每个 l 都重新往右扫一遍，整体还是太慢。

第一步：把问题看成“最短覆盖区间”

题目本质上是在问：

最短的连续区间
要覆盖全部 m 种画家编号

这就是一个非常典型的滑动窗口模型。

第二步：右端扩张，左端收缩

维护一个窗口 [l, r]：

cnt[x] 表示当前窗口里画家 x 出现了多少次
kind 表示当前窗口里已经包含了多少种不同画家

处理过程：

右端点 r 不断右移，把新画放进窗口
当 kind == m 时，说明当前窗口已经覆盖所有画家
这时尝试不断右移左端点 l，尽量缩短区间
只要缩到再缩就会丢失某种画家，就停止

这样每次得到的都是以当前 r 为右端时最短的合法区间。

第三步：为什么不会错过最优解

对固定的右端点 r：

当窗口第一次满足 `kind == m``
再不断右移 l

最后停下来的那个窗口，就是所有右端点为 r 的合法区间里最短的那个。

所以全程扫一遍后，最优答案一定会被枚举到。

另外，代码里只在“严格更短”时更新答案：

if (r - l < ans_r - ans_l)

这样当长度相同的时候，会自然保留更早出现的那个区间，也就满足“x 最小”的要求。

Python 知识

array("H") 用紧凑无符号短整数保存百万个不超过 2000 的画家编号。
计数归零时减少 covered，让窗口是否覆盖全部种类能在 $O(1)$ 判断。
只在严格更短时更新元组 (left, right)，自然保留最小左端点。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40import os
from array import array


def read_ints():
    number = 0
    reading = False
    while chunk := os.read(0, 1 << 20):
        for byte in chunk:
            if 48 <= byte <= 57:
                number = number * 10 + byte - 48
                reading = True
            elif reading:
                yield number
                number = 0
                reading = False
    if reading:
        yield number


data = iter(read_ints())
n, kinds = next(data), next(data)
artists = array("H", (next(data) for _ in range(n)))
counts = [0] * (kinds + 1)
left = covered = 0
answer = (0, n - 1)

for right, artist in enumerate(artists):
    if counts[artist] == 0:
        covered += 1
    counts[artist] += 1
    while covered == kinds:
        if right - left < answer[1] - answer[0]:
            answer = (left, right)
        counts[artists[left]] -= 1
        if counts[artists[left]] == 0:
            covered -= 1
        left += 1

print(answer[0] + 1, answer[1] + 1)

复杂度

时间复杂度： $O(n)$
空间复杂度： $O(m)$

总结

这题最关键的是先看出它不是普通区间枚举，而是：

最短覆盖全部种类的连续区间

一旦识别成这个模型，标准做法就是：

右端扩张补齐种类
左端收缩压缩长度

目录

题意

思路

第一步：把问题看成“最短覆盖区间”

第二步：右端扩张，左端收缩

第三步：为什么不会错过最优解

Python 知识

代码

复杂度

总结