曾有你的森林 尺取法板子题

板子题"/>

曾有你的森林 尺取法板子题

链接：
来源：牛客网

题目描述

Emiya面前的n朵花按直线排列,一共m种花朵,花的种类用1,2,3…m-1,m的数字进行编号..

Emiya想知道的是,最少连续多少朵花,可以包含前1~k种类花朵每种至少一次.

输入描述:

第一行包含一个整数T,表示测试的组数, 1≤T≤10

接下来是T组数据:

每组的第一行包含3个整数n,m,k 其中1 <= n,m <= 10^5,1 <= k <= m

接下来一行包含n个整数,表示按直线排列的n朵花.

输出描述:

每一组数据输出一行,包含一个整数包含,即为所求的答案.,如果不存在答案 则输出-1

样例

输入

3
5 5 3 
1 2 3 4 5
5 5 3 
1 2 1 2 1
5 4 3 
1 2 4 3 1

输出

3
-1
4

题解

尺取法板子题，不解释了。和 POJ - 3320  这道题方法一样

POJ - 3320 链接 

代码

#include<algorithm>
#include <iostream>
#include<cstring>
#include<map>
#include <cstdio>
using namespace std;
const int maxn=1e5+10;
int a[maxn];
int main(){int t;cin>>t;while(t--){int n,m,k;map<int,int> mm;scanf("%d%d%d",&n,&m,&k);for(int i=0;i<n;i++){scanf("%d",a+i);}int ans=1000000;int r=0,l=0,cnt=0;while(true){while(r<n&&cnt<k){mm[a[r]]++;if(mm[a[r]]==1&&a[r]<=k) cnt++;r++;}if(cnt<k) break;ans=min(ans,r-l);mm[a[l]]--;if(mm[a[l]]==0&&a[l]<=k) cnt--;l++;}if(ans==1000000){printf("-1\n");}else{printf("%d\n",ans);}}return 0;
}