洛谷 P2564 [SCOI2009]生日礼物 题解【贪心】【堆】【线段树】【two-pointer】

作者: wjyyy 分类: two-pointer,,线段树,解题报告,贪心 发布时间: 2018-08-05 20:19

点击量:200

 

    是一个贪心,不过解法比较多。

 

题目描述

小西有一条很长的彩带,彩带上挂着各式各样的彩珠。已知彩珠有N个,分为K种。简单的说,可以将彩带考虑为x轴,每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠,但多个彩珠也可以出现在同一个位置上。

 

小布生日快到了,于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮,小西希望这一段彩带中能包含所有种类的彩珠。同时,为了方便,小西希望这段彩带尽可能短,你能帮助小西计算这个最短的长度么?彩带的长度即为彩带开始位置到结束位置的位置差。

 

输入输出格式

输入格式:

第一行包含两个整数N, K,分别表示彩珠的总数以及种类数。接下来K行,每行第一个数为Ti,表示第i种彩珠的数目。接下来按升序给出Ti个非负整数,为这Ti个彩珠分别出现的位置。

 

输出格式:

输出应包含一行,为最短彩带长度。

 

输入输出样例

输入样例#1:

6 3
1 5
2 1 7
3 1 3 8

输出样例#1:

3

说明

【样例说明】

有多种方案可选,其中比较短的是1~5和5~8。后者长度为3最短。

 

【数据规模】

对于50%的数据, N≤10000;

 

对于80%的数据, N≤800000;

 

对于100%的数据,1≤N≤1000000,1≤K≤60,0≤Ti<$ 2^{31}$。

 

题解:

    这个题可以先排序,从左到右做,每次更新这个颜色最后一次出现的位置,放入线段树。如果所有颜色都出现过,就去线段树中查询所有颜色最后一次出现时间的最小值。每次更新当前位置与这个最小值之差的最小值作为答案,时间复杂度为$ O(N(\log n+\log k))$。线段树长度只用开$ k$即可。

 

    正解是类似two-pointer的尺取法,也就是先排序,从左到右找,定义一个左端点初始化为0。每次找到一个新的颜色就把前面的颜色打上删除标记,等找到全部颜色以后就从左端点开始枚举,把左端点调整到第一个没有删除标记的位置,这就是到当前位置的最优答案。

    当我们第一次发现所有的颜色,是在第7个位置,此时的左端点为1,我们从左边开始检索,找到第一个没有被删除的位置:2。那么我们找到的第一个答案就是7-2=5,更新到最小值中去。再继续遍历,发现2,此时把左边的2删除,这时左端点可以被移到4号位置去,更新最小值就是8-4=4。时间复杂度是$ O(N\log N+K)$

 

    不过这个题的数据规模是$ 10^6$,跑$ O(N\log N)$的排序有的评测机就可能吃不消。我们其实还可以优化。

 

    注意到题目给出的位置都是升序,那联想到归并排序合并的过程,我们只要每次找到$ k$列中剩下的最小的元素取出来不就可以了吗。在$ k$列中找最小只需要一个$ k$大小的堆就可以了。这样排序,对于很小很小的$ k$来说,近似$ O(N)$。时间复杂度为$ O(N\log K+K)$。

 

Code of two-pointer:

#include<cstdio>
#include<cstring>
#include<vector>
using std::vector;//因为不知道每一种颜色有多少个所以用vector
struct node
{
    int c,v;
    node(int c,int v)
    {
        this->c=c;
        this->v=v;
    }
    node()
    {}
    friend bool operator <(node a,node b)
    {return a.v<b.v;}

    friend bool operator >(node a,node b)
    {return a.v>b.v;}

}h[128],b[1000100];
int l=0;
//手写堆部分,优化常数
void push(node k)
{
    h[++l]=k;
    int i=l;
    while(i>1&&h[i]<h[i>>1])
    {
        node t=h[i];
        h[i]=h[i>>1];
        h[i>>1]=t;
        i>>=1;
    }
    return;
}
void pop()
{
    int i=1;
    h[1]=h[l--];
    while((i<<1)<=l&&(h[i]>h[i<<1]||h[i]>h[i<<1|1]))
        if((i<<1)==l||h[i<<1]<h[i<<1|1])
        {
            node t=h[i];
            h[i]=h[i<<1];
            h[i<<1]=t;
            i<<=1;
        }
        else
        {
            node t=h[i];
            h[i]=h[i<<1|1];
            h[i<<1|1]=t;
            i=i<<1|1;
        }
    return;
}
vector<int> v[66];
int tt[66],now[66];//tt是总共的个数,now是现在的个数,用于堆排序
int lst[66];//某种颜色上一次出现的位置
int used[66];//颜色出现过没有,used[0]表示一共出现了多少种颜色
int del[1000100],st=1;//删除标记和左端点
int main()
{
    memset(lst,0,sizeof(lst));
    int n,k,u;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)
        now[i]=1;
    for(int i=1;i<=k;i++)
    {
        scanf("%d",&tt[i]);
        for(int j=1;j<=tt[i];j++)
        {
            scanf("%d",&u);
            v[i].push_back(u);
        }
    }

    for(int i=1;i<=k;i++)
        push(node(i,v[i][0]));
    for(int i=1;i<=n;i++)//排序过程
    {
        b[i]=h[1];
        pop();
        if(now[b[i].c]<tt[b[i].c])
            push(node(b[i].c,v[b[i].c][now[b[i].c]]));
        now[b[i].c]++;
    }
    int ans=0x7fffffff;
    for(int i=1;i<=n;i++)
    {
        if(!used[b[i].c])
        {
            used[b[i].c]=1;
            used[0]++;
        }
        del[lst[b[i].c]]=true;
        lst[b[i].c]=i;
        if(used[0]==k)
        {
            while(del[st])//删除该删除的
                st++;
            ans=ans<(b[i].v-b[st].v)?ans:(b[i].v-b[st].v);//更新答案
        }
    }
    printf("%d\n",ans);
    return 0;
}

Code of Segment tree:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define Mid (t[k].l+t[k].r>>1)
int Min(int x,int y)
{
    return x<y?x:y;
}
struct node
{
    int l,r,v;
    node(int l,int r)
    {
        this->l=l;
        this->r=r;
        v=-1;
    }
    node()
    {
        v=-1;
    }
}t[500];
void build(int k,int l,int r)
{
    t[k]=node(l,r);
    if(l==r)
        return;
    build(ls,l,mid);
    build(rs,mid+1,r);
}
void change(int k,int p,int x)
{
    if(t[k].l==t[k].r)
    {
        t[k].v=x;
        return;
    }
    if(p<=Mid)
        change(ls,p,x);
    else
        change(rs,p,x);
    t[k].v=Min(t[ls].v,t[rs].v);
    return;
}
int ask(int k,int l,int r)
{
    if(t[k].l==l&&t[k].r==r)
        return t[k].v;
    if(r<=Mid)
        return ask(ls,l,r);
    else if(l>Mid)
        return ask(rs,l,r);
    else
        return Min(ask(ls,l,Mid),ask(rs,Mid+1,r));
}

struct ball
{
    int c,p;
    friend bool operator <(ball a,ball b)
    {
        return a.p<b.p;
    }
}a[1000010];
int cnt=0;
int main()
{
    int n,k,t,u;
    scanf("%d%d",&n,&k);
    build(1,1,k);
    for(int i=1;i<=k;i++)
    {
        scanf("%d",&t);
        for(int j=1;j<=t;j++)
        {
            scanf("%d",&u);
            a[++cnt].c=i;
            a[cnt].p=u;
        }
    }
    std::sort(a+1,a+1+n);
    int ans=0x7fffffff;
    for(int i=1;i<=n;i++)
    {
        change(1,a[i].c,a[i].p);
        int tmp=ask(1,1,k);//更新最晚值
        if(tmp==-1)//为-1说明还有颜色没找到
            continue;
        ans=ans<(a[i].p-tmp)?ans:(a[i].p-tmp);
    }
    printf("%d\n",ans);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */