P1638. 逛画展

发表于 分类于 阅读次数： Waline： 本文字数： 229 阅读时长 ≈ 1 分钟

考点

  • 双指针
  • 滑动窗口

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 50;
int n, m, ansa, ansb, a[maxn], c[maxn];

int main() {
  cin >> n >> m;
  int len = 0x3f3f3f3f;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int cnt = 0, l = 1, r = 1; l <= r && r <= n; ++r) {
    // 右指针向右扩张窗口
    if (c[a[r]]++ == 0) ++cnt;
    // 满足条件的情况下，左指针向右收缩寻找最短长度
    while (cnt == m) {
      if (len > r - l + 1) len = r - l + 1, ansa = l, ansb = r;
      if (--c[a[l++]] == 0) --cnt;
    }
  }
  cout << ansa << " " << ansb;
  return 0;
}

思路

滑动窗口的模板题，题意是要你寻找一个满足条件的最短窗口长度

设计思路很明显：

  • 窗口设计为“左闭右闭区间”，条件处理和可行性判定在本次完成

  • 只要没有满足条件，右指针向右扩张窗口

  • 只要满足条件，左指针向右收缩窗口寻找最短长度