习题 8-17 最短子序列（Smallest Sub-Array，UVa11536）

本文主要是介绍习题 8-17 最短子序列（Smallest Sub-Array，UVa11536），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://vjudge.net/problem/UVA-11536
分类：滑动窗口
备注：尺取法，简单题

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000005;
int t,n,m,k,a[maxn],vis[105];
int main(void){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);scanf("%d",&t);for(int i=1;i<=3;i++)a[i]=i;for(int kase=1;kase<=t;kase++){scanf("%d %d %d",&n,&m,&k);memset(vis,0,sizeof(vis));vis[1]=vis[2]=vis[3]=1;int num=3,L=1,ans=n;for(int i=4;i<=n;i++){a[i]=(a[i-1]+a[i-2]+a[i-3])%m+1;if(a[i]<=k&&!vis[a[i]]){num++; vis[a[i]]=1;}}printf("Case %d: ",kase);if(num<k){printf("sequence nai\n");continue;}num=0; memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++){if(a[i]<=k){vis[a[i]]++;if(vis[a[i]]==1)num++;}while(L<i&&(a[L]>k||vis[a[L]]>1)){if(a[L]<=k)vis[a[L]]--; L++;}if(num==k)ans=min(ans,i-L+1);}printf("%d\n",ans);}return 0;
}

这篇关于习题 8-17 最短子序列（Smallest Sub-Array，UVa11536）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---