问题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]区间里包含有用的数值

来源/分类

枚举 桶 计数 
[提交] [状态]