lp2564 SCOI2009 生日礼物

尺取法即可。
开一个桶维护珍珠的颜色，然后扫一遍。每一次将最前端的点弹出，然后移动至下一个合法点。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=1000005;
struct data{
	int id;
	int val;
}a[N];
inline bool cmp(const data &A,const data &B){
	return A.val<B.val;
}
int n,K,tp=0;
int bckt[65],cnt=0;
void init(){
	scanf("%d%d",&n,&K);
	int T;
	for(int i=1;i<=K;++i){
		scanf("%d",&T);
		for(int j=1;j<=T;++j){
			++tp;
			scanf("%d",&a[tp].val);
			a[tp].id=i;
		}
	}
	std::sort(a+1,a+1+n,cmp);
	int ans=2147483647;
	int l=1,r=0;
	while(r<n){
		while(r<n){
			++r;
			if(!bckt[a[r].id]){
				++cnt;
			}
			++bckt[a[r].id];
			if(cnt==K){
				break;
			}
		}
		if(cnt==K){
			ans=min(ans,a[r].val-a[l].val);
		}
		while(l<=r){
			--bckt[a[l].id];
			if(!bckt[a[l].id]){
				--cnt;
				++l;
				break;
			}
			++l;
			if(cnt==K){
//				printf("%d %d %d\n",ans,l,r);
				ans=min(ans,a[r].val-a[l].val);
			}
			
		}
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}