杭电2158-最短区间版大家来找碴

本文主要是介绍杭电2158-最短区间版大家来找碴，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最短区间版大家来找碴

Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 580 Accepted Submission(s): 184

Problem Description

给定一个序列，有N个整数，数值范围为[0,N)。
有M个询问，每次询问给定Q个整数，可能出现重复值。
要求找出一个最短区间，该区间要包含这Q个整数数值。
你能找的出来吗？

Input

第一行有两个整数N，M。(N<100000, M<1000)接着一行有N个整数。再有M个询问，每个询问的第一行有一个整数Q(Q<100)，第二行跟着Q个整数。当N,M同时为0时，输入结束。

Output

请输出最短区间的长度。保证有解。

Sample Input

Sample Output

  3
2Hint

第二个查询，找到的区间是[4,5]
AC代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<iomanip>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
const int MAX=100001;
using namespace std;
int a[MAX],d[MAX];
bool f[MAX],g[MAX];
int main()
{int n,m,k,sum,x;bool flag;while(scanf("%d%d",&n,&m)!=EOF){if(n==0&&m==0)break;for(int i=1; i<=n; i++)scanf("%d",&a[i]);while(m--){for(int i=1; i<=n; i++){d[i]=0;f[i]=g[i]=false;}flag=false;sum=0;scanf("%d",&k);for(int i=1; i<=k; i++){scanf("%d",&x);if(!f[x]){f[x]=true;//记录查询区间里面要查询的数g[x]=true;//为了初始化pt2的值sum++;}}int s=0,pt1=1,pt2=1;for(; s<sum; pt2++){d[a[pt2]]++;//确定每个数出现的次数if(g[a[pt2]]){s++;g[a[pt2]]=false;}}pt2--;int ans=pt2;if(pt2==1)flag=true;for(; pt1<=pt2&&!flag; pt1++){d[a[pt1]]--;if(f[a[pt1]]&&!d[a[pt1]]){if(ans>pt2-pt1+1){ans=pt2-pt1+1;if(ans==1){flag=true;break;}}pt2++;while(pt2<=n&&!flag){d[a[pt2]]++;if(a[pt2]==a[pt1])break;pt2++;}if(!d[a[pt1]])flag=true;}}printf("%d\n",ans);}}return 0;
}

这篇关于杭电2158-最短区间版大家来找碴的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！