前言
希望大家看后都能学会,也请大家多多点赞,谢谢。
我真的很想获奖。
算法介绍
区间伸缩,是一种基于单调性的算法。
它往往可以用来解决查询满足条件的最大区间这类的问题。
大致结构是这样的:
while(r<=n)
{
if(满足条件)l++;
else r++;
}
它经常是和单调队列一起使用的,也可以用其他数据结构维护。
时间复杂度是的。
我们先来看道例题让大家更深入的了解:逛画展
题意:
博物馆里有n幅画,每幅画都有一个作者,作者编号1-m。
问你最小的一个区间,使所有的画家都有画在这个区间里。
解题思路:
用两个变量和来枚举区间
如果到的区间不满足要求,
如果到的区间满足要求,记录答案,
我们先来讲一下为什么能这样做。
我们先假设,这个区间是刚好合法的,那么左端点变成,右端点会怎么变呢?右端点要么不变,要么向右移动。
想一想,为什么?这是不是就是满足单调性。
代码:
#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;
}
考一考
现在,让我来考考大家吧。
怎么样,很简单吧。
题解:
这题和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) 回帖