[SCOI2009]生日礼物 (尺取)

题目链接

题意：
$有k种彩珠总共n个，分别在彩带的某个位置x$
$找一个最短距离包括所有彩珠$
题解：
$n<=1e6,k<=60$
$区间统计问题$
$就可以考虑尺取，并且k比较小，可以进行判断$
$将所有彩珠的位置进行排序，然后依次进行种类的更新$
$然后直接进行Ok判断是不是每个种类的彩珠都有即可$
$每次如果有全部种类，就可以更新答案，找最小值$

/*Author : zzugzxLang : C++Blog : blog.csdn.net/qq_43756519 */
#include<bits/stdc++.h>
using namespace std;#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
#define mem(a, b) memset(a, b, sizeof(a))typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1e9 + 7;
//const int mod = 998244353;const double eps = 1e-6;
const double pi = acos(-1.0);
const int maxn = 1e6 + 10;
const int N = 1e2 + 5;
const ll inf = 0x3f3f3f3f;
const int dir[][2]={{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
int n, k;
int cnt[maxn];
bool ok() {for (int i = 1; i <= k; i++)if (!cnt[i]) return 0;return 1;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);cin >> n >> k;vector<pii> v;for (int i = 1; i <= k; i++) {int t;cin >> t;while (t--) {int x;cin >> x;v.pb(mp(x, i));}}sort(all(v));int ans = inf, l = 0;for (int r = 0; r < n; r++) {cnt[v[r].se]++;while (ok()) ans = min(ans, v[r].fi - v[l].fi), cnt[v[l++].se]--;}cout << ans << endl;return 0;
}