最短區間版大家來找碴
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; }