北京当地网站 点,广州海珠区有什么好玩的景点,网站制作多久,广告投放软件P1638 逛画展 - 洛谷 | 计算机科学教育新生态
这道题我们只要用一个kind和一个mp[N]的数组就能解决了 我们的解法1就是暴力枚举#xff0c;先固定2#xff0c;从2开始找连续的满足所有种类的最短的子数组#xff0c;然后固定5#xff0c;3#xff0c;1#xff0c;3…
P1638 逛画展 - 洛谷 | 计算机科学教育新生态
这道题我们只要用一个kind和一个mp[N]的数组就能解决了 我们的解法1就是暴力枚举先固定2从2开始找连续的满足所有种类的最短的子数组然后固定53132分别找出满足所有种类的最短子数组
mp[i]如果是从0到1kind如果是从1到0kind--
如图暴力枚举的话j指向的一定是第一次出现的最新的元素种类如果我们是暴力枚举的话我们枚举5的时候j也会回到5
我们对5枚举的时候j一定会再走到4那个位置我们何必让j回退呢
那我们的算法流程就是用left和right指针指向第一个元素然后让right指针向后走把每个元素进窗口如果kind种类够了的话left不断再不断更新每个合法的子数组的大小直到kind不够了再退出去继续right向后走
比如这是一种结果2出窗口后又是一个结果
5出窗口后种类不够了j向后走 不满足要求就不更新结果直到再次符合要求我们再次让left出窗口 到这里把3出窗口之后再次成为不合法数组 再次合法继续出left出了一个就不合法了right向后走一格结束
我们来展示一下代码
#include iostream
using namespace std;const int N 1e610;
int n,m;
int mp[N];
int a[N];
int main()
{cin n m;for(int i 1;in;i) cin a[i];int kind 0;int left 1 , right 1;int ret n,begin 1;while(rightn){if(mp[a[right]] 0) kind;while(kind m){int len right-left1;if(len ret){ret len;begin left;}if(mp[a[left]]-- 1) kind--;left;} right;}cout begin beginret-1 endl;return 0;
}
