NC21775. 曾有你的森林,あなたがいた森
描述
「深い深い森の中,ほのか香る,爱しい
日々の面影,探してみれば,ふいにあなたが笑う
「我问你。你是我的master吗？」
「我要去达成身为servant的责任。想传达之事，就留待之后吧」
「——总算注意到了，原来士郎 ，就是我的剑鞘呢。」
「对不起————士郞……」
多年以后,Emiya游历了Altria生前待过的地区.
一天,他到了Altria获得湖之精灵祝福,并拿到湖中剑[Excalibur]的地方
Emiya面前的nn朵花按直线排列,一共m种花朵,花的种类用1,2,3…m-1,m的数字进行编号..
输入描述
第一行包含一个整数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
C++14(g++5.4) 解法, 执行用时: 207ms, 内存消耗: 7288K, 提交时间: 2019-02-16 11:07:29
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+500;
int a[N],vis[N];
int T,n,m,k,cnt;
int main() {
scanf("%d",&T);
while(T--) {
memset(vis,0,sizeof vis);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
cnt=k;
int l,r=0,ans=1e9;
for(l=1;l<=n;l++) {
while(cnt&&r<n) {
if(a[r+1]<=k&&!vis[a[r+1]]) cnt--;
++r;++vis[a[r]];
}
if(!cnt) ans=min(ans,(r-l+1));
if(a[l]<=k&&vis[a[l]]==1) cnt++;
--vis[a[l]];
}
printf("%d\n",ans==1e9?-1:ans);
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 208ms, 内存消耗: 1252K, 提交时间: 2020-02-27 13:43:19
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+500;
int a[N],vis[N];
int T,n,m,k,cnt;
int main()
{
scanf("%d",&T);
while(T--)
{
memset(vis,0,sizeof vis);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
cnt=k;
int l,r=0,ans=1e9;
for(l=1;l<=n;l++)
{
while(cnt&&r<n)
{
if(a[r+1]<=k&&!vis[a[r+1]]) cnt--;
++r;
++vis[a[r]];
}
if(!cnt) ans=min(ans,(r-l+1));
if(a[l]<=k&&vis[a[l]]==1) cnt++;
--vis[a[l]];
}
printf("%d\n",ans==1e9?-1:ans);
}
return 0;
}