三类贪心区间覆盖问题

2019-08-16 07:47:21来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

三类贪心区间覆盖问题

一、区间完全覆盖问题

题目

给定一个长度为m的区间,再给出n条线段的起点和终点(注意这里是闭区间),求最少使用多少条线段可以将整个区间完全覆盖。

解析

先将所有线段按起点从小到大排序。排完序后,枚举每一个线段(被其它线段包含的线段不用考虑,因为很明显包含它的线段比它更优),将其作为最左端的线段,

再在剩下的左端点小于等于最左端的线段的右端点的线段中(若没有则无解),找到右端点最大的一个线段,即贪心,很显然这是最优的,因为其左端都被最左端的线段覆盖了,

也就没有覆盖到任何地方,则其右端点越大,其右端覆盖到的地方也就最优。

反复重复上一步,直到覆盖完整个长度为m的区间,就能得到最少的线段数。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
struct rec{
    int l,r;
}a[1001];
bool cmp(rec x,rec y)
{
    return x.l<y.l;        //按左端点从小到大排 
}
int m,n,ll,minn=0x7f7f7f7f;
void q(int x,int ans)
{
    if(a[x].r-ll>=m-1)    //覆盖总长度达到 
    {
        minn=min(minn,ans);
        return ;
    }
    int temp=0;
    for(int i=x+1;i<=n;i++)
    {
        if(a[i].l<=a[x].r)    //找左端点小于当前线段右端点的 
        {
            if(a[i].r>a[temp].r) temp=i;    //找右端点最大区间 
        }
        else break;        //顺序排序,如果左端点大于当前线段右端点,后面肯定也大于 
        if(temp!=0) q(temp,ans+1);
    }
}
int main()
{
    a[0].r=-1;    //特殊处理 
    cin>>m>>n;
    for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].r;
    sort(a+1,a+n+1,cmp);    //顺序排序 
    for(int i=1;i<=n;i++)
    {
        ll=a[i].l;        //记录起点 
        q(i,1);
    }
    cout<<minn;
    return 0;
}
View Code

 

 

 

 

 

 

 

二、最大不相交区间数问题

题目

数轴上有n个开区间[ai,bi],要求选择尽量多个区间,使得这些区间两两没有公共点。

解析

先对区间左端点进行从大到小排序,左端点相同按右端点从小到大排序,
再依次选出左端点最大的区间,当待选择区间与已选区间集合相交时,舍弃待选区间,
每次直接从排好后的第一个开始选,是为了使左边预留区间最大。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>     
using namespace std;
struct rec{
    int a,b;
}ra[1001];
bool cmp(rec x,rec y)
{
    if(x.a!=y.a) return x.a>x.b;//左端点从大到小排序
    else return y.a<y.b; //左端点相同,按右端点从小到大排序,即左端点相同,优先选择短的
}
int n,ans=1,lasta;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>ra[i].a>>ra[i].b;
    sort(ra,ra+n,cmp);
    lasta=ra[0].a;//选中a最大的第一个
    for(int i=1;i<n;i++)
    {
        if(ra[i].b<=lasta)    //不重叠 
        {
            lasta=ra[i].a;
            ans++;
        }
    }
    cout<<ans;
    return 0;
}
View Code

 

 

 

 

 

 

 

三、区间选点问题

题目

数轴上有n个闭区间 [ai,bi],要求选取尽量少的点,使得每个区间内都至少有一个点(不同区间内含的点可以是同一个)。

解析

先按左端点从小到大排序每个区间,若左端点相同,则按右端点从小到大排序。

1.再从第一个区间贪心往后找,如果下一个区间左端点大于该区间的右端点,则需增加一个点,反之共用一个点;

2.若下个区间右端点小于当前区间右端点,说明共用的区间范围变小了,则更新区间右端点为下一个区间右端点。

不断重复1、2两个步骤,直到每个区间都有点。

为什么呢?因为在排完序后,

①当b1>bi时,显然此时一个点能覆盖最大的区域右边界变为bi

②当b1<ai时,显然一个点不能覆盖到区间i上,所以需新开一个点,此时能覆盖的区域最右边界变为bi

③ 当b1<bi时,显然区间1和区间i有公共的部分,但此时一个点能覆盖的区域最右边界还是为b1,无需更新区域最右边界

综上所述,排序后贪心选点是正确的。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>     
using namespace std;
struct rec{
    int a,b;
}ra[1001];
bool cmp(rec x,rec y)
{
    if(x.a!=y.a) return x.a<y.a;    //按左端点从小到大排序 
    else return x.b<y.b;        //左端点相同,则按右端点从小到大排序 
}
int n,ans=1,r;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>ra[i].a>>ra[i].b;
    sort(ra+1,ra+n+1,cmp);        //顺序排序
    r=ra[1].b;    //记录上一个区间右端点 
    for(int i=2;i<=n;i++)
    {
        if(ra[i].a>r)    //左端点大于上个区间右端点 
        {
            ans++;        //增加一个点 
            r=ra[i].b;
        }
        else if(ra[i].b<r) r=ra[i].b;    //右端点小于上个区间右端点,更新上个区间右端点 
    }
    cout<<ans;
    return 0;
}
View Code

 


原文链接:https://www.cnblogs.com/I-Love-You-520/p/11147003.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:“直男”与“暖男”的区别——const

下一篇:金明的预算方案