首页 > 代码库 > [bzoj1293][SCOI2009]生日礼物

[bzoj1293][SCOI2009]生日礼物

给定n个k种礼物,没种礼物有一定的数量和坐标,你要选择最短的一段,使得这一段上有全部k种礼物。 n<=1000000

题解:很容易想到排序以后,两个坐标推一推 就没啦。

#include<iostream>
#include<cstdio>
#include<algorithm>
#define MAXN 1000000
#define INF 2147483647
using namespace std;
inline int read()
{
    int x = 0 , f = 1; char ch = getchar();
    while(ch < 0 || ch > 9){ if(ch == -) f = -1;  ch = getchar();}
    while(ch >= 0 && ch <= 9){x = x * 10 + ch - 0;ch = getchar();}
    return x * f;
}

struct N{
    int k,x;
}s[MAXN+5];
int n,k,tot=0,kind=0,ans=INF;
int num[66];

bool cmp(N x,N y){return x.x<y.x;}

void ins(int x){if(++num[x]==1)kind++;}
void del(int x){if(--num[x]==0)kind--;}

int main()
{
    n=read();k=read();
    for(int i=1;i<=k;i++)
    {
        int nn=read();
        for(int j=1;j<=nn;j++)
            s[++tot].k=i,s[tot].x=read();
    }
    sort(s+1,s+n+1,cmp);
    ins(s[1].k);
    for(int l=1,r=1;l<=n;del(s[l++].k))
    {
        while(kind<k&&r<n) ins(s[++r].k);
        if(kind==k)
            ans=min(ans,s[min(r,n)].x-s[l].x);
        else break;
    }
    cout<<ans;
    return 0;
}

 

[bzoj1293][SCOI2009]生日礼物