洛谷P2564 [SCOI2009]生日礼物（单调队列）

传送门

 

准确的来说这个应该叫尺取法？

先对所有的点按$x$坐标进行排序

我们维护两个指针$l,r$，每一次令$r$不断右移直到所有颜色齐全，再不断右移$l$直到颜色数不足，那么此时$[l-1,r]$这个区间里的彩珠肯定能构成所有颜色，且不难发现不会有包含这一区间的方案比它更优

//minamoto
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
inline int read(){
    #define num ch-'0'
    char ch;bool flag=0;int res;
    while(!isdigit(ch=getc()))
    (ch=='-')&&(flag=true);
    for(res=num;isdigit(ch=getc());res=res*10+num);
    (flag)&&(res=-res);
    #undef num
    return res;
}
const int N=1e6+5;
struct node{
    int x,col;
    inline bool operator <(const node &b)const
    {return x<b.x;}
}a[N];
int cnt[105],tot,n,k,res=inf;
inline void add(int i){if(++cnt[a[i].col]==1) ++tot;}
inline void del(int i){if(--cnt[a[i].col]==0) --tot;}
int main(){
//    freopen("testdata.in","r",stdin);
    n=read(),k=read();
    for(int i=1;i<=k;++i){
        int x=read();
        for(int j=1;j<=x;++j) a[++tot].x=read(),a[tot].col=i;
    }
    tot=0,sort(a+1,a+1+n);
    int l=1,r=0;
    while(true){
        while(tot<k&&r<n) add(++r);
        if(r==n&&tot<k) break;
        while(tot==k&&l<=r) del(l++);
        cmin(res,a[r].x-a[l-1].x);
    }
    printf("%d\n",res);
    return 0;
}