[SCOI2009]生日礼物

写在前面

没给出数据范围，差评。

补充一下数据范围：

「数据规模」
对于50%的数据， N≤10000；
对于80%的数据， N≤800000；
对于100%的数据，1≤N≤1000000，1≤K≤60，0≤彩珠位置<2^31。

分析

考虑尺取法，说白了就是双指针。

先对 x 排个序，然后利用一个数组记录当前区间每个颜色的出现次数，然后我们不断推进左端点，当左右端点区间颜色种类达到 k 的时候，再推进右端点，一直推进到左右端点区间颜色种类数恰好不是 k 个，一直重复这个过程就好了。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1001110;
int n,k;

struct node
{
    int col,x;
    bool operator < (const node tmp) const
    {
        return x < tmp.x;
    }
}a[maxn];

int cnt[maxn];

signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>k;
    int m,x;
    n = 0;
    for(int i = 1; i <= k; i++) 
    {
        cin>>m;
        for(int j = 1; j <= m; j++) 
        {
            cin>>x;
            a[++n].col = i;
            a[n].x = x;
        }
    }
    sort(a+1,a+1+n);
    int l = 1,ans = 1e9,res=0;
    for(int i = 1; i <= n; i++) 
    {   
        if(cnt[a[i].col] == 0) res++;
        cnt[a[i].col]++;
        while(res == k)
        {
            int tmp = a[i].x-a[l].x;
            ans = min(ans,tmp);

            cnt[a[l].col]--;
            if(cnt[a[l].col] == 0) res--;
            l++;
        }
    }
    cout<<ans<<endl;
    return 0;
}