数轴上有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:区间选点问题
内容简介: 涵盖 - 选择不相交区间问题 & - 区间覆盖问题 & ...五大贪心问题模板与解析。 适合人群: 普及晚期或提高早期的萌新 OIer 们。 (参考并整合自《信息学奥赛一本通——提高篇》)
超详细的 FabMaster 选点操作指南,至于软件,太大,需要的联系我吧
FabMaster是经典的传统的而非常优秀的ICT 治具 选点分析软件,至今仍有很多工程师在使用。电路板的可测性设计(DFT,Design For Test)是十分重要的。熟悉使用它仍是必要而有用的,它可以帮助工程师提高电路板的可测性...
百度地图拖拽选点 可显示经纬度 经纬度: 地址: 最近的路口 最近的路 最近的POI
百度地图选点定位
本标准目的为了规范ICT测试针床选点的步骤方法,避免针床选点遗漏及不合理针点出现的情况,在源头上保证测试的稳定性及可靠性,最大程度保证ICT测试的可测率。 2 适用范围: 适用于本工厂内所有涉及到测试治具的部门...
地图选点google.zip
本程序设计了Qt界面,实现了点云显示、屏幕选点、调节颜色等功能。屏幕选点功能中,按住shift并选择相应的点,即可选中该点,目前功能并不完善,需要滑动滑块才能更新显示坐标。开发环境为vs2015+pcl1.8.1+Qt5.11.2+...
本组件是用于在地图上选点、回显坐标等
Android版仿微信发送位置、地图选点(高德地图). 前面上传过一个百度地图的, 这个也一起上传吧(捞点分, 现在下载都强制需要资源分), Key请自行申请, demo包含一个可运行apk和源码.
针对ict测试的PCB精准选点,多项选点规则精要,着重选点的实用及准确度,以提供ict测试的准确性.
三类基于贪心算法覆盖问题先按b从小到大进行排序,再选择b0作为选点pos,以每个村庄坐标为圆心,D为半径画圆,与X轴有两个交点,得到一个区间,得到N个区间后,就转化为了
其实就是MATLAB里的一个函数啦 不是那个自动配准工具箱 这个是需要手动选点的 选完之后直接关掉页面就会自动算单应矩阵了,然后后面可以显示出来看看对的齐不齐,我后面应该加了些切割图像的代码(因为变完会显示...
section辅助工具2中利用区选点,这是一个GIF的图片简单易懂。
使用matlab从图像上手动选取点,并返回选取点的像素坐标
手动选点并根据点的相同,实现图像拼接,需要精准的选点。
治具制作分析和选点。以及使用的说明,操作四线的方法
抽水蓄能电站选点规划编制规范,适用水电专业