竞赛讨论区 > 尺取法-区间伸缩-算法介绍
头像
xuxuxuxuxu
发布于 2019-04-18 18:40
+ 关注

尺取法-区间伸缩-算法介绍

前言

希望大家看后都能学会,也请大家多多点赞,谢谢。

我真的很想获奖。

算法介绍

区间伸缩,是一种基于单调性的算法。

它往往可以用来解决查询满足条件的最大区间这类的问题。

大致结构是这样的:

while(r<=n)
{
    if(满足条件)l++;
    else r++;
}

它经常是和单调队列一起使用的,也可以用其他数据结构维护。

时间复杂度是O(n)的。

我们先来看道例题让大家更深入的了解:逛画展

题意:

博物馆里有n幅画,每幅画都有一个作者,作者编号1-m。
问你最小的一个区间,使所有的画家都有画在这个区间里。

解题思路:

用两个变量lr来枚举区间

如果lr的区间不满足要求,

如果lr的区间满足要求,记录答案,

我们先来讲一下为什么能这样做。

我们先假设l,r这个区间是刚好合法的,那么左端点变成,右端点会怎么变呢?右端点要么不变,要么向右移动。

想一想,为什么?这是不是就是满足单调性。

代码:

#include
using namespace std;
int n,m,a[1000005],b[2005],k,ans,l,r,ll,rr;
//b[i]表示当前区间画家i的图画数
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    l=1; r=1; k=1; b[a[1]]=1; ans=1000005;
    //k记录当前区间中有多少画家的图画
    while(l<=r && r<=n)
    {
        if(k==m)//判断是否符合要求
        {
            if(ans>r-l+1)   
            {
                ans=r-l+1;//ans记录最小区间长度
                ll=l; rr=r;
    //ll记录最小区间的左端点,rr记录最小区间的右端点
            }
            b[a[l]]--;
            if(b[a[l]]==0) k--;
            l++;
        }
        else{
            r++;
            b[a[r]]++;
            if(b[a[r]]==1) k++;
        }
    }
    printf("%d %d",ll,rr);
    return 0;
}

我们再来看到题:[USACO12MAR]花盆Flowerpot

这也是区间伸缩的模板题。

这题的难点就在于一些边界,细节和如何判断区间合法。

判断区间合法,我们只要找到最大值和最小值,只要他们的差大于d就是满足条件的。

找最大值和最小值可以用单调队列,st表也可以用线段树。(本蒟蒻用的是线段树)

边界和细节就是每次要把同一横坐标的点都一起做。

代码:

#include
using namespace std;
struct node{
    int x,y;
};
struct tr{
    int maxx,minn;
};
tr tree[4000005];
int n,m,u,v,ans,l,r;
node a[1000005];
bool cmp(node a,node b)
{
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}
void build(int nod,int l,int r)//线段树建树
{ 
    if(l==r)
    {
        tree[nod].minn=a[l].y;
        tree[nod].maxx=a[l].y;
        return;
    }
    int mid=(l+r)/2;
    build(nod*2,l,mid);
    build(nod*2+1,mid+1,r);
    tree[nod].minn=min(tree[nod*2].minn,tree[nod*2+1].minn);
    tree[nod].maxx=max(tree[nod*2].maxx,tree[nod*2+1].maxx);
}
int findmaxx(int nod,int l,int r,int ll,int rr)//查询区间max
{
    if(l==ll&&r==rr) return tree[nod].maxx;
    int mid=(l+r)/2;
    if(rr<=mid) return findmaxx(nod*2,l,mid,ll,rr);
    else if(ll>mid) return findmaxx(nod*2+1,mid+1,r,ll,rr);
    else return max(findmaxx(nod*2,l,mid,ll,mid),findmaxx(nod*2+1,mid+1,r,mid+1,rr));
}
int findminn(int nod,int l,int r,int ll,int rr)//查询区间min
{
    if(l==ll&&r==rr) return tree[nod].minn;
    int mid=(l+r)/2;
    if(rr<=mid) return findminn(nod*2,l,mid,ll,rr);
    else if(ll>mid) return findminn(nod*2+1,mid+1,r,ll,rr);
    else return min(findminn(nod*2,l,mid,ll,mid),findminn(nod*2+1,mid+1,r,mid+1,rr));
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
    sort(a+1,a+n+1,cmp);//以x轴排序
    build(1,1,n);
    l=1;r=1;ans=100000000;
    for(int i=2;i<=n;i++)
        if(a[i].x==a[1].x)r++;//把x轴相同的点一加入
        else break;
    while(l<=r && r<=n)
    {
        if(findmaxx(1,1,n,l,r)-findminn(1,1,n,l,r)>=m)//满足条件
        {
            if(a[r].x-a[l].x<ans) ans=a[r].x-a[l].x;//更新答案
            l++;
            if(l>n) break;//注意边界
            while(a[l].x==a[l-1].x)
            {
                l++;
                if(l>n) break;//注意边界
            } 
        }
        else{//不满足条件
            r++;
            if(r>n) break;//注意边界
            while(a[r+1].x==a[r].x)
            {
                r++;
                if(r>n) break;//注意边界
            }
        }
    }
    if(ans==100000000) cout<<-1<<endl;
    else printf("%d",ans);
    return 0;
}

考一考

现在,让我来考考大家吧。

题目:[SCOI2009]生日礼物

怎么样,很简单吧。

题解:

这题和P1638 逛画展很像,几乎就是一模一样。

唯一的区别就是可能同一个位置上可能都有多个"彩珠"。

然而有多个"彩珠"这点有和P2698[USACO12MAR]花盆Flowerpot这题一样

代码:

#include
using namespace std;
const int N=1000005;
int l,r,n,m,k,t,b[105],cnt,ans;
//cnt记录当前区间有几种不同的颜色
struct node{
    int val,id;
}a[N];
bool cmp(node a,node b)
{
    return a.val<b.val;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&k);
        for(int j=1;j<=k;j++)
        {
            scanf("%d",&a[++t].val);
            a[t].id=i;
        }
    }
    ans=1e9;
    sort(a+1,a+t+1,cmp);//排序是为了使位置相同的"彩珠"在一起
    l=r=1;b[a[1].id]=1;cnt=1;
    for(int i=2;i<=n;i++)
        if(a[i].val==a[i-1].val)
        {
            r++;
            b[a[i].id]++;
            if(b[a[i].id]==1)cnt++;
        }
        else break;
    //注意每次要把同一个位置的"彩珠"全部算
    while(l<=n&&r<=n)
    {
        if(cnt==m)//满足条件
        {
            ans=min(ans,a[r].val-a[l].val);
            b[a[l].id]--;if(b[a[l].id]==0)cnt--;
            l++;if(l>n)break;//注意边界
            while(a[l].val==a[l-1].val)
            {
                b[a[l].id]--;if(b[a[l].id]==0)cnt--;
                l++;if(l>n)break;//注意边界
            }
        }
        else{//不满足条件
            r++;if(r>n)break;//注意边界
            b[a[r].id]++;if(b[a[r].id]==1)cnt++;
            while(a[r+1].val==a[r].val)
            {
                r++;if(r>n)break;//注意边界
                b[a[r].id]++;if(b[a[r].id]==1)cnt++;
            }
        }
    }
    cout<<ans;
}

最后,来一道牛客普及比赛的T4:数糖纸

题解:

这题真简单,和前面的做法都一样。

就是这题的颜色种类很多有1e9,这怎么办?

对了,n很小只有1e6,我们可以离散化一下颜色,然后就好了。

代码:

#include
using namespace std;
const int N=2e6+5;
int n,l,r,cnt,len,ans,a[N],b[N];
bool v[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    len=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+len+1,a[i])-b;
    l=r=1;v[a[1]]=true;cnt=1;
    while(l<=n&&r<=n)
    {
        ans=max(ans,r-l+1);
        if(cnt==len)
        {
            v[a[l]++]=false;
            cnt--;
        }
        else{
            if(!v[a[r+1]])
            {
                v[a[++r]]=true;
                cnt++;
            }
            else{
                v[a[l++]]=false;
                cnt--;
            }
        }
    }
    printf("%d",ans);
    return 0;
}

完结撒花,谢谢大家,记得点赞哦。

如有写错的地方请私信我,有不懂的也可私信我。

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐