ZYF004 逛画展
大约 1 分钟
ZYF004 逛画展
【算法】 双指针、滑动窗口
【C++】 双指针、cnt数组
【难度】 普及−
一、题目简述
幅画,每幅画属于某一位名师(编号 )。找最短的连续区间 ,使得能看到所有 位名师的画。多解时输出 最小的。
二、解题思路
双指针滑动窗口,维护窗口内每位名师出现的次数。
- 右移,加入
- 当窗口包含所有 位名师时,尝试缩小 (右移 去掉多余)
- 记录最短区间
手动模拟 [2,5,3,1,3,2,4,1,1,5,4,3], m=5:
- r 不断右移,直到包含所有 5 种(到 r=7 时包含 2,5,3,1,4)
- l 从 1 开始缩小:l=1 去掉 2(还有),l=2 去掉 5(没了!不能去)
- 最短区间 [2,7],长度 6
继续扫描寻找更短的,最终 [2,7]。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int a[N], cnt[2005]; // m <= 2000
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
int l = 1, kinds = 0; // 当前不同种类数
int bestLen = n + 1, bestL = 1;
for (int r = 1; r <= n; r++) {
if (cnt[a[r]] == 0) kinds++;
cnt[a[r]]++;
while (kinds == m) { // 已包含所有名师
if (r - l + 1 < bestLen) {
bestLen = r - l + 1;
bestL = l;
}
cnt[a[l]]--;
if (cnt[a[l]] == 0) kinds--;
l++;
}
}
cout << bestL << " " << bestL + bestLen - 1 << endl;
return 0;
}四、复杂度分析
- 时间复杂度:。每个元素最多进出窗口一次。
- 空间复杂度:,使用
cnt数组记录每种画的出现次数。
