博主主页：Yu·仙笙

配套资源：三类基于贪心算法覆盖问题-C++文档类资源-CSDN下载

专栏：C++知识精讲

目录

三类基于贪心思想的区间覆盖问题

情形1：区间完全覆盖问题

描述：

样例：

解题过程:

例题：

题意：

例题：

例题二：

思路：

情形2：最大不相交区间数问题

例题：

输入格式：

输出格式：

思路：

情形3：区间选点问题。

描述

输入

输出

样例输入

样例输出

练习：POJ 3485 Highway

大意：

Sample Input

Sample Output

思路：

---

三类基于贪心思想的区间覆盖问题

情形1：区间完全覆盖问题

描述：

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

样例：

区间长度8，可选的覆盖线段[2,6],[1,4],[3,6],[3,7],[6,8],[2,4],[3,5]

解题过程:

1将每一个区间按照左端点递增顺序排列，拍完序后为[1,4]，[2,4]，[2,6]，[3,5]，[3,6]，[3,7]，[6,8]

2设置一个变量表示已经覆盖到的区域。再剩下的线段中找出所有左端点小于等于当前已经覆盖到的区域的右端点的线段中，右端点最大的线段在加入，直到已经覆盖全部的区域

3过程:

假设第一步加入[1,4]，那么下一步能够选择的有[2,6]，[3,5]，[3,6]，[3,7]，由于7最大，所以下一步选择[3,7]，最后一步只能选择[6,8]，这个时候刚好达到了8退出，所选区间为3

4贪心证明:

需要最少的线段进行覆盖，那么选取的线段必然要尽量长，而已经覆盖到的区域之前的地方已经无所谓了，（可以理解成所有的可以覆盖的左端点都是已经覆盖到的地方），那么真正能够使得线段更成的是右端点，左端点没有太大的意义，所以选择右端点来覆盖

例题：

Intervals(http://poj.org/problem?id=1089

Description

There is given the series of n closed intervals [ai; bi], where i=1,2,...,n. The sum of those intervals may be represented as a sum of closed pairwise non−intersecting intervals. The task is to find such representation with the minimal number of intervals. The intervals of this representation should be written in the output file in acceding order. We say that the intervals [a; b] and [c; d] are in ascending order if, and only if a <= b < c <= d.

Task

Write a program which:

reads from the std input the description of the series of intervals,

computes pairwise non−intersecting intervals satisfying the conditions given above,

writes the computed intervals in ascending order into std output

Input

In the first line of input there is one integer n, 3 <= n <= 50000. This is the number of intervals. In the (i+1)−st line, 1 <= i <= n, there is a description of the interval [ai; bi] in the form of two integers ai and bi separated by a single space, which are respectively the beginning and the end of the interval,1 <= ai <= bi <= 1000000.

Output

The output should contain descriptions of all computed pairwise non−intersecting intervals. In each line should be written a description of one interval. It should be composed of two integers, separated by a single space, the beginning and the end of the interval respectively. The intervals should be written into the output in ascending order.

Sample Input

5

5 6

1 4

10 10

6 9

8 10

Sample Output

1 4

5 10

题意：

求区间最大覆盖

#include <iostream>#include <vector>#include <algorithm>#include <cstring>#include <cstdio>#include <cmath>using namespace std;const int maxn=50000+20;struct area{int l,r;}a[maxn];int cmp(area x,area y){if(x.l==y.l)return x.r<y.r;return x.l<y.l;}int main(){int ans,la,lb,n,i;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d%d",&a[i].l,&a[i].r);if(a[i].l>a[i].r)swap(a[i].l,a[i].r);}sort(a+1,a+n+1,cmp);la=a[1].l;lb=a[1].r;for(i=2;i<=n;i++){if(a[i].l>lb){printf("%d %d\n",la,lb);la=a[i].l;lb=a[i].r;}else {lb=max(lb,a[i].r);}}printf("%d %d\n",la,lb);return 0;}

例题：

[NOIP2005 普及组] 校门外的树 - 洛谷

#include<bits/stdc++.h>using namespace std;const int maxn=100+20;struct area{int l,r;}a[maxn];int cmp(area x,area y){if(x.l==y.l)return x.r<y.r;return x.l<y.l;}int main(){int ans,la,lb,n,i,L;scanf("%d%d",&L,&n);for(i=1;i<=n;i++){scanf("%d%d",&a[i].l,&a[i].r);if(a[i].l>a[i].r)swap(a[i].l,a[i].r);}sort(a+1,a+n+1,cmp);ans=L+1;la=a[1].l;lb=a[1].r;for(i=2;i<=n;i++){if(a[i].l>lb){ans-=lb-la+1;la=a[i].l;lb=a[i].r;}else {lb=max(lb,a[i].r);}}ans-=lb-la+1;cout<<ans<<endl;return 0;}

例题二：

思路：

对于输入的每个点,先用勾股定理求出能覆盖住矩形的起点和终点,然后进行一次排序,如果最小的起点和最大的终点都不能超过矩形的长度范围,则必定无解,取出起始点最靠前的点,然后记录下这个点的终点,遍历这个起点到终点范围内的所有其他的点,并挑选其中终点最靠后的那个点作为下一个终点的位置,并且计数器加一,继续向后遍历,如果有区间接不上,则表明无解,成功遍历到矩形最后,则直接输出计数器的值

#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>using namespace std;const int maxn=10000+10;struct area{double l,r;}a[maxn];int cmp(area x,area y){if(x.l==y.l)return x.r<y.r;else return x.l<y.l;}int main(){int t,n,w,flag,i,tot,x,ans,pos;double h,tmp,lb,r;scanf("%d",&t);while(t--){scanf("%d%d%lf",&n,&w,&h);h=h/2;//矩形的高tot=0;//共tot个矩形覆盖for(i=1;i<=n;i++){scanf("%d%lf",&x,&r);tmp=sqrt(r*r-h*h);//计算矩形的宽if(tmp>0){a[++tot].l=max(0.0,x*1.0-tmp);a[tot].r=x*1.0+tmp;}}sort(a+1,a+tot+1,cmp);ans=0;flag=1;pos=1;lb=0;//前pos个区间能覆盖的最大区间for(;lb<w;){tmp=0;for(i=pos;a[i].l<=lb&&i<=tot;i++){tmp=max(tmp,a[i].r);//左边界在lb以内能覆盖到的最远距离}if(tmp>lb){ans++;//增加一个喷头lb=tmp;//更新lbpos=i;//更新pos}else {//无法往后覆盖flag=0;break;}}if(flag)printf("%d\n",ans);else printf("0\n");}return 0;}

情形2：最大不相交区间数问题

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

贪心策略：

按照b1<=b2<=b3…的方式排序，然后从前向后遍历，每当遇到可以加入集合的区间，就把它加入集合。（集合代表解的集合）

证明：

我们对a1,a2……的关系分以下几种情况考虑：

1、a1>a2。   此时区间2包含区间1。这种情况下显然不会选择区间2，因为选择区间1会留下更多的剩余空间。

不仅区间2如此，以后所有区间中只要有一个 i 满足a1 > ai，i 都不要选。

即此种情况下，选择区间1是明智的，与策略一致。

2、排除情况1后，一定有a1<=a2<=a3……。

例题：

线段覆盖

已知数轴上0<N<10000条线段。每条线段按照端点Ai和Bi（Ai<>Bi,i=1..N）定义。端点坐标在（-999，999）内，坐标为整数。有些线段可能相交。编程实现删除最少数目的线段，使得余下的任意两条线段不相交。

输入输出格式

输入格式：

第一行为一整数N。接下来有N行，每行包含两个整数 (Ai 和 Bi), 用空格隔开。

输出格式：

整数p，即删除后余下的线段数。

输入输出样例

输入样例#1：

3

6 3

1 3

2 5

输出样例#1：

2

思路：

贪心思想，时间复杂度O(nlog(n))

1. 数据给出个端点可能逆序，需判断处理。

2. 排序，将每一个区间按右端点进行递增顺序排列

3.第一个区间必可保留，记录保留区间的最大右边界为pos,遍历区间i，如果a[i].l>pos，则可保留区间增加，并且pos更新为a[i].r。

#include<bits/stdc++.h>#define MaxInt 100000using namespace std;const int maxn=10000+20;struct line{int l,r;}a[maxn];int n;int cmp(line x,line y){return x.r<y.r;}int main(){int i;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d%d",&a[i].l,&a[i].r);if(a[i].l>a[i].r)swap(a[i].l,a[i].r);}sort(a+1,a+n+1,cmp);int ans=1,pos=a[1].r;for(i=2;i<=n;i++)if(a[i].l>=pos){ans++;pos=a[i].r;}printf("%d",ans);return 0;}

情形3：区间选点问题。

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

贪心思想：

先按b从小到大进行排序，再选择b0作为选点pos，如果出现ai>pos，则以bi作为pos，再按照这样的方式迭代。直至所有区间遍历完。

描述

上数学课时，老师给了LYH一些闭区间，让他取尽量少的点，使得每个闭区间内至少有一个点。但是这几天LYH太忙了，你们帮帮他吗？

输入

多组测试数据。

每组数据先输入一个N，表示有N个闭区间（N≤100)。

接下来N行，每行输入两个数a，b(0≤a≤b≤100），表示区间的两个端点。

输出

输出一个整数，表示最少需要找几个点。

样例输入

4

1 5

2 4

1 4

2 3

3

1 2

3 4

5 6

1

2 2

样例输出

1

3

1

#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>using namespace std;const int maxn=100+10;struct area{int l,r;}a[maxn];int cmp(area x,area y){if(x.r==y.r)return x.l<y.l;else return x.r<y.r;}int main(){int n,i,pos,ans;while(scanf("%d",&n)!=EOF){for(i=1;i<=n;i++)scanf("%d%d",&a[i].l,&a[i].r);sort(a+1,a+n+1,cmp);ans=1;pos=a[1].r;for(i=2;i<=n;i++){if(a[i].l>pos){ans++;pos=a[i].r;}}printf("%d\n",ans);}return 0;}

练习：POJ 3485 Highway

大意：

X轴上公路从0到L，X轴上下有一些点给出坐标代表村庄，问在公路上最少建几个出口才能使每个村庄到出口的距离不超过D。

Sample Input

100

50

3

2 4

50 10

70 30

Sample Output

1

1

思路：

以每个村庄坐标为圆心，D为半径画圆，与X轴有两个交点，得到一个区间，得到N个区间后，就转化为了区间选点问题。策略为：先按区间的右端点从小到大排序，如果相同则按左端点从大到小排序。
 

#include <iostream>#include <string.h>#include <stdio.h>#include <cmath>#include <algorithm>using namespace std;struct point{    double left;    double right;}po[100000];int cmp(const void *a,const void *b){    return (*(point*)a).right < (*(point*)b).right ? -1 : 1;}int main(){    double way_long,dis;    int n,i,j,k;    double a,b;    double rec;    int re;    while(scanf("%lf%lf%d",&way_long,&dis,&n)!=EOF)    {        re=0;        for(i=0;i<n;i++)        {        scanf("%lf%lf",&a,&b);        rec=sqrt(dis*dis-b*b);        po[i].left=a-rec;        po[i].right=a+rec;        if(po[i].left < 0)        po[i].left=0;        }        qsort(po,n,sizeof(po[0]),cmp);       // for(i=0;i<n;i++)        //printf("%lf\n",po[i].right);        re=0;        i=0;        while(i<n)        {            k=i;            re++;            while(i<n && po[i].left <= po[k].right) i++;        }        printf("%d\n",re);    }    return 0;}