`
lovnet
  • 浏览: 6670868 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

区间选点问题(贪心)

 
阅读更多

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

贪心策略:

按照b1<=b2<=b3…(b相同时按a从大到小)的方式排序排序,从前向后遍历,当遇到没有加入集合的区间时,选取这个区间的右端点b。

证明:

为了方便起见,如果区间i内已经有一个点被取到,我们称区间i被满足。

1、首先考虑区间包含的情况,当小区间被满足时大区间一定被满足。所以我们应当优先选取小区间中的点,从而使大区间不用考虑。

按照上面的方式排序后,如果出现区间包含的情况,小区间一定在大区间前面。所以此情况下我们会优先选择小区间。

则此情况下,贪心策略是正确的。

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


对于区间1来说,显然选择它的右端点是明智的。因为它比前面的点能覆盖更大的范围。

从而此情况下,贪心策略也是正确的。

例题:http://acm.nyist.net/JudgeOnline/problem.php?pid=287

附代码(非此例题代码)。(和选择不相交区间问题的十分相似)

#include <stdio.h>
#include <algorithm>
using namespace std;
struct Extent
{
    int a,b;
    bool operator < (const Extent& S)const
    {
        return b < S.b || b == S.b && a > S.a;
    }
}A[10002];
int main()
{
    int z,n,cnt,end;
    scanf("%d",&z);
    while(z--)
    {
        cnt = 0;
        end = -1;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%d%d",&A[i].a,&A[i].b);
        sort(A,A+n);
        for(int i=0;i<n;i++)
        {
            if(end < A[i].a)
            {
                end = A[i].b;
                cnt++;
            }
        }
        printf("%d\n",cnt);
    }
	return 0;
}




分享到:
评论

相关推荐

    贪心思想的区间覆盖问题

    情形1:区间完全覆盖问题 情形2:最大不相交区间数问题 情形3:区间选点问题

    C++ 贪心算法的 5 大问题模板与解析

    内容简介: 涵盖 - 选择不相交区间问题 & - 区间覆盖问题 & ...五大贪心问题模板与解析。 适合人群: 普及晚期或提高早期的萌新 OIer 们。 (参考并整合自《信息学奥赛一本通——提高篇》)

    FabMaster 选点操作指南

    超详细的 FabMaster 选点操作指南,至于软件,太大,需要的联系我吧

    FabMaster ICT选点分析培训

    FabMaster是经典的传统的而非常优秀的ICT 治具 选点分析软件,至今仍有很多工程师在使用。电路板的可测性设计(DFT,Design For Test)是十分重要的。熟悉使用它仍是必要而有用的,它可以帮助工程师提高电路板的可测性...

    百度地图拖拽选点

    百度地图拖拽选点 可显示经纬度 经纬度: 地址: 最近的路口 最近的路 最近的POI

    百度地图选点定位demo

    百度地图选点定位

    测试工装选点 规范

    本标准目的为了规范ICT测试针床选点的步骤方法,避免针床选点遗漏及不合理针点出现的情况,在源头上保证测试的稳定性及可靠性,最大程度保证ICT测试的可测率。 2 适用范围: 适用于本工厂内所有涉及到测试治具的部门...

    地图选点google.zip

    地图选点google.zip

    Qt+pcl+vtk 屏幕选点

    本程序设计了Qt界面,实现了点云显示、屏幕选点、调节颜色等功能。屏幕选点功能中,按住shift并选择相应的点,即可选中该点,目前功能并不完善,需要滑动滑块才能更新显示坐标。开发环境为vs2015+pcl1.8.1+Qt5.11.2+...

    vue+地图选点组件(百度地图)

    本组件是用于在地图上选点、回显坐标等

    仿微信发送位置、地图选点(高德地图)

    Android版仿微信发送位置、地图选点(高德地图). 前面上传过一个百度地图的, 这个也一起上传吧(捞点分, 现在下载都强制需要资源分), Key请自行申请, demo包含一个可运行apk和源码.

    PCB选点规则

    针对ict测试的PCB精准选点,多项选点规则精要,着重选点的实用及准确度,以提供ict测试的准确性.

    三类基于贪心算法覆盖问题

    三类基于贪心算法覆盖问题先按b从小到大进行排序,再选择b0作为选点pos,以每个村庄坐标为圆心,D为半径画圆,与X轴有两个交点,得到一个区间,得到N个区间后,就转化为了

    MATLAB手动选点配准图像

    其实就是MATLAB里的一个函数啦 不是那个自动配准工具箱 这个是需要手动选点的 选完之后直接关掉页面就会自动算单应矩阵了,然后后面可以显示出来看看对的齐不齐,我后面应该加了些切割图像的代码(因为变完会显示...

    section利用区选点

    section辅助工具2中利用区选点,这是一个GIF的图片简单易懂。

    matlab从图像上选点

    使用matlab从图像上手动选取点,并返回选取点的像素坐标

    MATLAB.rar_matlab gui中选点_matlab图中选点_matlab点_mosaicking_选点

    手动选点并根据点的相同,实现图像拼接,需要精准的选点。

    华笙软件的分析与选点

    治具制作分析和选点。以及使用的说明,操作四线的方法

    抽水蓄能电站选点规划编制规范

    抽水蓄能电站选点规划编制规范,适用水电专业

Global site tag (gtag.js) - Google Analytics