题目

一道模拟和队列题，但模拟比队列的成分多一些。队列也就是用两个指针模拟的。

可以用枚举的思想。首先我们知道r(即区间的右端点是肯定不会左移的)，而l右移的同时，r可能不变，也可能右移，所以这样就可以不用\(O(n^2)\)处理了，剩下的就只剩下模拟的细节。

#include <bits/stdc++.h>

#include <queue>

using namespace std;

struct ha {

	int a, x;

}data[1010011];

int n, k, cnt, minn = 2147483647, tong[100100];//tong表示桶

bool cmp(ha a, ha b)

{

	return a.x < b.x;

}

int main()

{

	scanf("%d%d", &n, &k);

	for (int i = 1; i <= k; i++)

	{

		int t; scanf("%d", &t);

		while (t--)

		{

			scanf("%d", &data[++cnt].x);

			data[cnt].a = i;

		}

	}

	sort(data + 1, data + 1 + cnt, cmp);

	int l = 0, r = 0;

	int sum = 0;

	while (r < n)

	{

		while (r < n && sum < k)

		{

			if (sum == k) break;

			r++;

			tong[data[r].a]++;

			if (tong[data[r].a] == 1)

			sum++;

		}

		l++;

		minn = min(minn, data[r].x - data[l].x);

		if (tong[data[l].a] == 1)

		sum--;

		tong[data[l].a]--;

	}

	printf("%d", minn);

}