[SCOI2009]生日礼物

直接双指针模拟就好了,然后拿ans统计答案的min.注意变量之间别混淆.

//orz代码构思太弱了...
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
typedef long long ll;
struct vv{
    ll col,pos;
}a[N];
int cnt[N];//统计

bool cmp(vv x,vv y)
{
    if(x.pos==y.pos) return x.col<y.col;
    else             return x.pos<y.pos;
}

int main()
{
    int n,k,vnt=0;
    scanf("%d%d",&n,&k);
    n=0;
    for(int i=1;i<=k;i++)
    {
        int x;scanf("%d",&x);
        for(int j=1;j<=x;j++)
        {
            ++n;
            scanf("%lld",&a[n].pos);
            a[n].col=i;
        }
    }
    sort(a+1,a+1+n,cmp);
   // for(int i=1;i<=n;i++) cout<<a[i].col<<' ';
    //cout<<endl;
    ll l=1;ll ans=1e15;
    for(ll r=1;r<=n;r++)//枚举右端点.
    {
        //int x=a[r].pos;
        //cout<<a[r].col<<endl;
        cnt[a[r].col]++;
        if(cnt[a[r].col]==1) vnt++;
        //cout<<vnt<<endl;
        if(vnt==k)
        {
            while(cnt[a[l].col]>1) {cnt[a[l].col]--; l++; }
            ans=min(ans,a[r].pos-a[l].pos);
        }
    }
    printf("%lld\n",ans);
    return 0;
}