【贪心】区间覆盖
【题目描述】
给定一个长度为m的区间，再给出n条线段的起点和终点（本题考虑闭区间），求最少使用多少线段可以将整个区间完全覆盖。
【输入】
第一行是区间长度m。第二行是n,表示有n个可选区间。后面跟着n行数据，每行包含两个值，第一个是当前区间的起始端点值，第二个是当前区间的结束端点值。
【输出】
能覆盖m的最少的区间个数
【输入样例1】
8 6 2 6 1 4 3 6 3 7 6 8 2 4 3 5
【输出样例1】
3
【举例】
例如：M=5，整数1、3、4、8、11表示区间。
要求：所用线段不超过 N=3条。
【问题描述】
给定n个区间和一个范围[a, b],选择尽量少的区间，使得[a, b]能够被完全覆盖。
【题目分析】
注意题目要求是要用“线段”覆盖“区间”。如果有一个线段足够长，可以直接覆盖整个区间，那么一定就选它，否则就要选择尽可能少的“线段”来覆盖掉整个“区间”。
【贪心策略】
对于当前区间[a,b]来说，选择的下一个区间的左端点值a2一定不会大于b，否则就不能完成“覆盖”这一操作。 对于当前区间[a,b]来说，如果有多个区间都满足条件1，那么一定选择右端点最大的区间，否则就不能满足“最小”这一目的。
【思路】
将所有的区间按左端点从小到大排序，依次处理每个区间。每次选择覆盖点s的区间右端点坐标中最大的一个。并将更新为该区间的右端点坐标，直到选择的区间已经包含了t为止。 贪心策略：在某个时刻的s。找一个满足 a[i]<<s的b[i]最大值即可。
【贪心策略及证明】
要求用最少的线段进行覆盖，那么选取的线段必然要尽量长，而已覆盖到的区域之前的地方已经不用考虑了，可以理解成所有可覆盖的左端点都已经被覆盖了，那么能够使得线段更长的取决于右端点，左端点没有太大意义。
方法：
（1）先将n个区间按照起点进行递增排序。
（2）令s表示已经覆盖到的区域。再剩下的区间中找出所有左端点小于等于当前已经覆盖到的区域s并且右端点大于等于s的区间，取右端点最大的区间加入，直到已经覆盖全部的区域。
【求解过程】
将每一条线段按左端点递增排列，如果左端点相同，按右端点递增顺序排列，排序后为【1,4】【2，4】【2，6】【3，5】【3，6】【3，7】【6，8】
设置一个变量表示已覆盖到的区间右端点，在剩下的线段中找出所有左端点小于等于当前已覆盖到的区间右端点的线段，选择右端点最大并且大于当前已覆盖到的区间右端点，重复以上操作直至覆盖整个区间。
模拟过程：假设第一次加入【1，4】，那么下一次能够选择的线段有【2，6】【3，5】【3，6】【3，7】由于3小于4且7最大，所以下一次选择【3，7】进行覆盖，最后一次只能选择【6，8】，这个时候刚好覆盖长为8的区间—>break; 即所选3条线段就能覆盖长度为8的区间。
【伪代码】
while(剩余区间数目不为0)
{
if(总长度已经超出覆盖范围) {
结束循环;
}
for(循环查找符合条件的下一个最大区间)
if(找到了){
答案数+1;
总长度+=最大能切换的区间长度
}else{
表示不能完全覆盖， 退出循环 ，答案数=0
}
}【例题】
【题目描述】
有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n<=10000)个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。
【输入描述】
第一行输入一个正整数N表示共有n次测试数据。
每一组测试数据的第一行有三个整数n,w,h，n表示共有n个喷水装置，w表示草坪的横向长度，h表示草坪的纵向长度。
随后的n行，都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标（最左边为0），ri表示该喷水装置能覆盖的圆的半径。
【输出描述】
每组测试数据输出一个正整数，表示共需要多少个喷水装置，每个输出单独占一行。
如果不存在一种能够把整个草坪湿润的方案，请输出0。
【样例输入】
2 2 8 6 1 1 4 5 2 10 6 4 5 6 5
【样例输出】
1 2
【参考代码】
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
#define INF 1e-6 //双精度浮点数趋近于0的值
#define MAX 10005
struct Node {
double left;
double right;
} map[MAX];
int num_input = 0;
int length = 0;
int width = 0;
int cmp(Node a,Node b)
{
if(a.left != b.left) { //这里按左端点排序比较方便
return a.left < b.left;
}
return a.right < b.right;
}
double calue(int r)
{
double res;
res = (double)r*r - (double)width*width/4.0;
if(res >= INF) {
res = sqrt(res);
} else {
res = 0;
}
return res;
}
int main()
{
int time = 0;
scanf("%d", &time);
while(time--) {
scanf("%d%d%d", &num_input, &length, &width);
int a = 0;
int b = 0;
double res = 0;
for(int i = 0; i < num_input; i++) {
scanf("%d %d", &a, &b);
res = calue(b);
map[i].left = a - res;
map[i].right = a + res;
}
sort(map, map+num_input, cmp);
double sum = 0;
int ans = 0;
while(sum < length) {
double num_max = 0;
for(int i = 0; i < num_input && map[i].left <= sum; i++) {
num_max = max(num_max, map[i].right-sum);
}
if(0 == num_max) {
ans = 0;
break;
} else {
sum += num_max;
ans++;
}
}
printf("%d\n",ans);
}
return 0;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
