曾有你的森林,あなたがいた森

链接：https://ac.nowcoder.com/acm/contest/321/I

题目描述

「深い深い森の中,ほのか香る,爱しい

日々の面影,探してみれば,ふいにあなたが笑う

触れて见たくて,手を伸ばしても,儚く宙を舞ったのです.」

_____________________

「啊啊，你选了一条艰辛的道路呢,不过奇迹是需要代价的,亚瑟王啊。你将要以你最重要的事物去交换」

「我问你。你是我的master吗？」

「我要去达成身为servant的责任。想传达之事，就留待之后吧」

「——总算注意到了，原来士郎 ，就是我的剑鞘呢。」

「对不起————士郞……」

「…」

多年以后,Emiya游历了Altria生前待过的地区.

一天,他到了Altria获得湖之精灵祝福,并拿到湖中剑[Excalibur]的地方

湖边有很多不同的花,据说是Altria 的导师Merlin当时种下的.

_______________________

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

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

 

输入描述:

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

接下来是T组数据:

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

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

输出描述:

每一组数据输出一行,

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

示例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

 

题目中说了好多废话，我认为最关键的信息是：Emiya想知道的是,最少连续多少朵花,可以包含前1~k种类花朵每种至少一次

也就是说，要求的是最少的连续花数，保证前k种花每种至少一次。

 

 

 

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int maxx=1e9;
int a[maxn];
int q[maxn];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m,k;
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<n;i++)scanf("%d",&a[i]);
        memset(q,0,sizeof(q));
        int ans=maxx;
        int x=0;
        int l=0,r=0;
        while(r<n)
        {
            if(!q[a[r]]&&a[r]<=k)x++;
            q[a[r]]++;
            while(true)
            {
                if(a[l]>k)l++;
                else if(q[a[l]]>1&&a[l]<=k)q[a[l]]--,l++;
                else break;
            }
            if(x>=k){
                ans=min(ans,r-l+1);
            }
            r++;
        }
        if(x<k)ans=-1;
        printf("%d\n",ans);
    }
}