P1638 逛画展
逛画展
题目描述
博览馆正在展出由世上最佳的 𝑚位画家所画的图画。
游客在购买门票时必须说明两个数字，𝑎 和 b，代表他要看展览中的第 𝑎 幅至第 𝑏 幅画（包含 𝑎,𝑏）之间的所有图画，而门票的价钱就是一张图画一元。
Sept 希望入场后可以看到所有名师的图画。当然，他想最小化购买门票的价格。
请求出他购买门票时应选择的 𝑎,𝑏数据保证一定有解。
若存在多组解，输出 𝑎 最小的那组。
输入格式
第一行两个整数 𝑛,𝑚，分别表示博览馆内的图画总数及这些图画是由多少位名师的画所绘画的。
第二行包含 𝑛 个整数 𝑎𝑖，代表画第 𝑖 幅画的名师的编号。
输出格式
一行两个整数 a,b。
样例 #1
样例输入 #1
12 5
2 5 3 1 3 2 4 1 1 5 4 3
样例输出 #1
2 7
提示
数据规模与约定
对于 30% 的数据，有 n≤200，m≤20。
对于 60% 的数据，有 n≤10^5，m ≤10^3。
对于 100% 的数据，有 1≤n≤106，1≤ai≤m≤2×103。
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> paintings(n + 1); // 保存每幅画对应的名师编号
for (int i = 1; i <= n; ++i) cin >> paintings[i];
unordered_map<int, int> cnt; // 记录每个名师画作的数量
int minLen = n + 1; // 初始化最小长度为n+1，即不可能的最大值
int l = 1, r = 1; // 初始化双指针
int ansStart = 1, ansEnd = n; // 初始化答案区间
// 首先扩展右边界，直到包含所有名师的画作
for (end = 1; end <= n; ++end) {
cnt[paintings[end]]++;
// 当区间包含所有名师的画作时，尝试缩小左边界
while (cnt.size() == m) {
if (end - start + 1 < minLen) {
minLen = end - start + 1;
ansStart = start;
ansEnd = end;
}
cnt[paintings[start]]--;
if (cnt[paintings[start]] == 0) {
cnt.erase(paintings[start]); // 如果某个名师的画作数为0，则从哈希表中删除
}
start++;
}
}
cout << ansStart << " " << ansEnd << endl;
return 0;
}