【传送门：BZOJ1293】
简要题意：
有一条很长很长的线段，线段上有很多个点，每个点上有若干个彩珠（也可以没有），彩珠有颜色，取出最短的线段长，使得这条线段上有所有颜色的彩珠
题解：
一开始空间开太大了，搞得T了好几遍
然后优化了一下下
记录每个彩珠的位置和颜色，然后把彩珠按照位置排一遍，然后用一个结构体来把彩珠分成几段，使得每段的位置相等
然后定义l和r为当前匹配到哪几段，然后用sum数组保存每种颜色彩珠出现的次数，kk表示出现的彩珠种数，一旦kk等于彩珠颜色种数就更新答案
这道题就搞定了
参考代码：
#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> using namespace std; struct node { int x,t; }a[1100000];int len; bool cmp(node n1,node n2) { return n1.x<n2.x; } int sum[61]; struct duan { int x,y; }b[1100000]; int main() { int n,k; scanf("%d%d",&n,&k); len=0; for(int i=1;i<=k;i++) { int t;scanf("%d",&t); for(int j=1;j<=t;j++) { int x; scanf("%d",&x); len++; a[len].x=x; a[len].t=i; } } sort(a+1,a+len+1,cmp); int cnt=1; b[cnt].x=1; for(int i=1;i<=len;i++) { if(a[i].x!=a[i+1].x) { b[cnt].y=i; if(i+1>len) break; b[++cnt].x=i+1; } } int l=1,r=0;int kk=0; int ans=1<<31-1; while(r<cnt) { r++; for(int i=b[r].x;i<=b[r].y;i++) { if(sum[a[i].t]==0) kk++; sum[a[i].t]++; } while(kk==k) { ans=min(ans,a[b[r].y].x-a[b[l].y].x); for(int i=b[l].x;i<=b[l].y;i++) { if(sum[a[i].t]==1) kk--; sum[a[i].t]--; } l++; } } printf("%d ",ans); return 0; }