问题1020--最短区间

1020: 最短区间

时间限制: 5 Sec  内存限制: 128 MB
提交: 213  解决: 33
[提交] [状态] [讨论版] [命题人:]

题目描述

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

输入

第一行有两个整数N,M。接着一行有N个整数。再有M个询问,每个询问的第一行有一个整数Q(Q<100),第二行跟着Q个整数。

输出

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

样例输入 Copy

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

样例输出 Copy

3
2

提示

【样例说明】
第二个查询,找到的区间是[4, 5]
【数据规模和约定】
(N<100000, M<1000)
题解: 区间找茬
设两个指针st=0,ed=0
分别扫描头和尾,不断伸缩头和尾,保证尽可能的在[st, ed]区间里包含有用的数值

来源/分类