題意：
? ? ? ? ? ? ? ? ?最短區(qū)間版大家來(lái)找碴


Problem Description
給定一個(gè)序列，有N個(gè)整數(shù)，數(shù)值范圍為[0,N)。有M個(gè)詢問(wèn)，每次詢問(wèn)給定Q個(gè)整數(shù)，可能出現(xiàn)重復(fù)值。要求找出一個(gè)最短區(qū)間，該區(qū)間要包含這Q個(gè)整數(shù)數(shù)值。
你能找的出來(lái)嗎？

Input
第一行有兩個(gè)整數(shù)N，M。(N<100000, M<1000)接著一行有N個(gè)整數(shù)。再有M個(gè)詢問(wèn)，每個(gè)詢問(wèn)的第一行有一個(gè)整數(shù)Q(Q<100)，第二行跟著Q個(gè)整數(shù)。當(dāng)N,M同時(shí)為0時(shí)，輸入結(jié)束。
?
Output
請(qǐng)輸出最短區(qū)間的長(zhǎng)度。保證有解。

?

Sample Input

5 2
1 2 2 3 1
3
1 2 3
3
1 1 3
0 0

Sample Output

3
2

Hint
第二個(gè)查詢，找到的區(qū)間是[4,5]

思路：

? ? ? 這個(gè)題目做的有點(diǎn)糾結(jié)，我的時(shí)間復(fù)雜度沒(méi)次詢問(wèn)都是O(N)的，那么一次測(cè)試的時(shí)間復(fù)雜度就是O(N*M)這樣是1e了，這樣估計(jì)就TLE了，但是卻AC了，雖然理論上測(cè)試數(shù)據(jù)是隨機(jī)數(shù)據(jù)，但是感覺(jué)還是有點(diǎn)勉強(qiáng)。我的思路是先找到一個(gè)最基本的L，R然后L不停的往后擠，然后維護(hù)R來(lái)保證當(dāng)前的區(qū)間的正確性，同時(shí)更新最小值（這次的代碼寫的有點(diǎn)挫-_-）.

#include<stdio.h> #include<string.h>#define N 110000 int num[N] ,markc[N] ,markq[N];int main () {int n ,m ,q ,a ,i;while(~scanf("%d %d" ,&n ,&m) && n + m){for(i = 1 ;i <= n ;i ++)scanf("%d" ,&num[i]);while(m--){scanf("%d" ,&q);memset(markc ,0 ,sizeof(markc));memset(markq ,0 ,sizeof(markq));int ss = 0;for(i = 1 ;i <= q ;i ++){scanf("%d" ,&a);if(!markq[a]) ss ++;markq[a] = 1;}int L ,R ,nowsum ,Ans;L = 1 ,nowsum = 0 ,Ans = n;//找到LR for(i = 1 ;i <= n ;i ++){if(markq[num[i]]) {if(!markc[num[i]]) nowsum ++;markc[num[i]] ++;if(nowsum == ss) {R = i;break;}}}Ans = R - L + 1; for(i = L ;i <= n ;i ++){if(markq[num[i]]) if(!(--markc[num[i]])){int ok = 0;for(int j = R + 1 ;j <= n ;j ++){if(markq[num[j]]){markc[num[j]] ++;if(num[j] == num[i]){ok = 1;R = j;break;}}}if(!ok) break;}if(Ans > R - i) Ans = R - i;}printf("%d\n" ,Ans);}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu2158 最短区间版大家来找碴的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。