C++知识精讲15 | 三类基于贪心思想的区间覆盖问题【配套资源详解】

这篇具有很好参考价值的文章主要介绍了C++知识精讲15 | 三类基于贪心思想的区间覆盖问题【配套资源详解】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

C++知识精讲15 | 三类基于贪心思想的区间覆盖问题【配套资源详解】

 

博主主页: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;

}

例题二:

C++知识精讲15 | 三类基于贪心思想的区间覆盖问题【配套资源详解】

思路:

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

#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;//更新lb

pos=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 100000

using 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个区间后,就转化为了区间选点问题。策略为:先按区间的右端点从小到大排序,如果相同则按左端点从大到小排序。
 文章来源地址https://www.toymoban.com/news/detail-408388.html

#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;
}

到了这里,关于C++知识精讲15 | 三类基于贪心思想的区间覆盖问题【配套资源详解】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++知识精讲13 | 原码、反码和补码

    ------------------------------------------------------------------------------------------------------------------------- 观看视频ing......  12岁的少年编程者告诉你编程如此简单  ------------------------------------------------------------------------------------------------------------------------- ---------------------------------------

    2024年02月16日
    浏览(36)
  • 区间覆盖 & 线段覆盖 & 二分

    4195. 线段覆盖 - AcWing题库 P2082 区间覆盖(加强版) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 做法: 差分解决区间覆盖:(这题不能过,但是感觉这个做法有用) 4195. 线段覆盖 - AcWing题库 问题描述: 坐标轴中共有多少个 整数坐标 的点满足恰好被 k条线段覆盖。 思路:离

    2024年02月12日
    浏览(38)
  • 区间覆盖问题

    区间覆盖问题,一般可以抽象为给定一些小区间 ,从中选择一些区间,能够覆盖 ,求最少选择多少个小区间的问题。 一般有两种做法: 贪心、动态规划。 贪心法基于这样的考虑: 因为x=s这个点是必须要被覆盖的,在可以覆盖到s的小区间里,选择右端点最大的小区间,是最优

    2024年02月09日
    浏览(33)
  • 【贪心算法part05】| 435.无重叠区间、763.划分字母区间、56.合并区间

    目录 🎈LeetCode435. 无重叠区间   🎈LeetCode763.划分字母区间 🎈LeetCode 56.合并区间 链接:435.无重叠区间 给定一个区间的集合  intervals  ,其中  intervals[i] = [starti, endi]  。返回  需要移除区间的最小数量,使剩余区间互不重叠  。    链接:763.划分字母区间 给你一个字符串

    2024年02月16日
    浏览(47)
  • 贪心算法part5 | ● 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间

    重叠问题都需要先排好序,再贪心 搞清楚左右区间,重叠的条件。 要找出最少删除的数量,也就是找出重叠空间的数量,然后用长度减去即可。 这里提供一种与452.用最少数量的箭引爆气球 (opens new window)、435.无重叠区间 (opens new window)相同的思路。 统计字符串中所有字符的

    2024年02月09日
    浏览(60)
  • 划分字母区间【贪心算法】

    划分字母区间 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。 注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s 。返回一个表示每个字符串片段的长度的列表。 参考下图: 1.确定每个元素的最

    2024年02月10日
    浏览(52)
  • 合并区间【贪心算法】

    合并区间 以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。

    2024年02月10日
    浏览(41)
  • 贪心算法(区间问题)

    有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中 points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend 之间的气球。你不知道气球的确切 y 坐标。 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭,若有一个气

    2024年03月11日
    浏览(69)
  • Leecode56:合并区间(贪心算法)

    第一眼看到这个题目觉得应该是比较第一个值的大小,因为如果第n个值比n-1个值的右边还小于等于,那么说明区间可以连起来。但是不会写比较强!! Arrays.sort()函数里, Arrays.sort(shuzu, Comparatorint[](){ }); 千万记得排序后分清楚哪个是原本的哪个是当前的!!以及新加一个

    2024年02月07日
    浏览(46)
  • 贪心算法思想详解+示例代码

    CSDN话题挑战赛第2期 参赛话题:学习笔记 分治思想 贪心算法/贪婪算法 动态规划 动态回溯 分支定界 今天我们来学习贪心算法。 什么是贪心算法,顾名思义,就是你要贪,做题要学会 贪 。 实际上,贪心算法就是 把大的问题归纳成小问题 ,然后得到解决的思想,贪心算法是

    2024年02月07日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包