最短区间版大家来找碴
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个整数数值。
你能找的出来吗？
有M个询问，每次询问给定Q个整数，可能出现重复值。
要求找出一个最短区间，该区间要包含这Q个整数数值。
你能找的出来吗？
Input
第一行有两个整数N，M。(N<100000, M<1000)接着一行有N个整数。再有M个询问，每个询问的第一行有一个整数Q(Q<100)，第二行跟着Q个整数。当N,M同时为0时，输入结束。
Output
请输出最短区间的长度。保证有解。
Sample Input
5 2 1 2 2 3 1 3 1 2 3 3 1 1 3 0 0
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; }