“奔跑吧,兄弟” 栏目组要在全国各地挑选节目录制的地点。有来自 K(1<=K<=100)个不同地区的 N(K<=N<=20,000)个选手送来了各自的竞选材料。由于参加的选手太多,没有办法同时呈现所有材料供评委进行选择。栏目组决定选择一段连续区间内的个人参选材料,这个区间内每个地区的参选选手至少要有 1名,求满足要求的最小区间长度。c++解决
时间: 2024-03-24 15:36:00 浏览: 17
```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 20010, K = 110;
int n, k;
int a[N], cnt[K];
int main() {
cin >> k >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
int left = 1, right = 0; // 初始化指针,表示区间[left, right]中没有元素
int res = n + 1; // 结果初始化为n+1,表示不存在满足条件的区间
while (right < n) { // 右指针扫描到最后一个元素时结束
right++;
cnt[a[right]]++; // 将右端点所在地区的计数器加1
while (left <= right && cnt[a[left]] > 1) { // 如果左端点所在地区的计数器大于1,说明该地区已经有多于1个选手参选,左指针右移
cnt[a[left]]--;
left++;
}
if (left <= right && right - left + 1 >= k) { // 如果区间满足要求,更新最小区间长度
res = min(res, right - left + 1);
}
}
cout << res << endl;
return 0;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)