NOIP 与区间有关的贪心汇总

总结一点实用(较基础)的内容

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]

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

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

证明: 我们其实考虑的是用最少的区间覆盖连续的最大的区间, 由于是所有都需要覆盖, 所以左端点影响不会特别大, 我们只是需要考虑右端点的情况就好了, 而且显然我们希望右端点越大越好.

problem : 喷水装置

背景:

有一块草坪,横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n<=10000)个点状的喷水装置,每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置,把整个草坪全部润湿.

分析:

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

也就是讲二维的面积覆盖转化成了一维区间覆盖, 同上做法就好了!

2.最大不相交区间数问题

也就是大家熟悉的”会议安排”问题!

做法:

按照b_1\leq b_2\leq b_3…的方式排序,然后从前向后遍历,每当遇到可以加入集合的区间,就把它加入集合。(集合代表解的集合)

证明:

  • a_1 > a_2 此时区间2包含区间1。这种情况下显然不会选择区间2,因为选择区间1会留下更多的剩余空间。不仅区间2如此,以后所有区间中只要有一个 i 满足a1 > ai,i 都不要选。 即此种情况下,选择区间1是明智的,与策略一致

排除这些情况之后, 只有x升序排列的情况了, 于是就好了!

3.区间选点问题

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

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注