一、区间完全覆盖问题
问题描述：给定一个长度为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]，由于3小于4且7最大，所以下一次选择[3, 7]进行覆盖，最后一次只能选择[6, 8]，这个时候刚好覆盖长为8的区间—>break；即所选3条线段就能覆盖长度为8的大区间。
贪心证明：
要求用最少的线段进行覆盖，那么选取的线段必然要尽量长，而已覆盖到的区域之前的地方已经不用考虑了，可以理解成所有可覆盖的左端点都已被覆盖了，那么能够使得线段更长的取决于右端点，左端点没有太大的意义，所以选择右端点来覆盖。
题解报告：NYOJ #12 喷水装置（二）
描述：
有一块草坪，横向长w、纵向长为h，在它的横向中心线上不同位置处装有n(n <= 10000) 个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被湿润。请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部湿润。
输入：
第一行输入一个正整数 N 表示共有 n 次测试数据。每一组测试数据的第一行有三个整数n,w,h，n表示共有 n 个喷水装置，w表示草坪的横向长度，h表示草坪的纵向长度。随后的n行，都有两个整数xi和ri、xi表示第i个喷水装置的横坐标（最左边为0），ri表示该喷水装置能覆盖的园的半径。
输出：
每组测试数据输出一个正整数，表示共需要多少个喷水装置，每个输出单独占一行。如果不存在一种能够把整个草坪湿润的方案，请输出0。
样例输入：
22 8 61 14 52 10 64 56 5
样例输出：
1
2
解题思路：典型的区间覆盖问题。由于喷水装置是安置在横向中心线上并且园具有对称性，故只需考虑高度的一半，然后将每个喷水装置能够覆盖的区间范围。
代码实现：
import java.util.*;
/**
* @author Jo
* @create 2020/8/25 15:26
* @description
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
List<Data> list;
for (int i = 0; i < n; i++) {
int num = 0, w = 0, h = 0;
list = new ArrayList<>();
num = scanner.nextInt();
w = scanner.nextInt();
h = scanner.nextInt();
for (int j = 0; j < num; j++) {
Data data = new Data();
data.left = scanner.nextInt(); // 暂时用来先存储它的坐标
double temp = scanner.nextInt(); // 能够喷的范围
temp = Math.sqrt(temp * temp - h / 2 * h / 2);
if (temp > h / 2) { // 如果能将上下左右喷完全咯，那才能加入list，否则丢掉
data.right = data.left + temp;
data.left = data.left - temp;
list.add(data);
}
}
// 排个序
list.sort((o1, o2) -> {
if (o1.left == o2.left) return 0;
return o1.left > o2.left ? 1 : -1;
});
double right = 0.0; // 保存当前已经覆盖的长度
int count = 0; // 需要的喷水装置的数量
while (right < w) {
double m = 0.0; // 用来存放当前的最优解
for (int j = 0; j < list.size() && list.get(j).left <= right; j++) {
if (list.get(j).right - right > m) {
m = list.get(j).right - right;
}
}
if (m != 0) {
count++;
right += m;
} else {
break;
}
}
if (right < w) System.out.println(-1);
else System.out.println(count);
}
}
static class Data {
public double left;
public double right;
}
}
注意：上面代码没有全部AC，以后修改。
题解报告：NYOJ #6 喷水装置（一）
描述：
现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri（0<Ri<15）的园被湿润，这有充足的喷水装置i（1<i<600）个，并且一定能把草坪全部湿润，你要做的是：选择尽量少的喷水装置，把整个草坪的全部湿润。
输入：
第一行m表示有m组测试数据；
每一组测试数据的第一行有一个整数n，n表示共有n个喷水装置，随后的一行，有n个实数ri，ri表示该喷水装置能覆盖的园的半径。
输出：
输出所用装置的个数。
样例输入：
2
5
2 3.2 4 4.5 6
10
1 2 3 1 2 1.2 3 1.1 1 2
样例输出：
2
5
解题思路：
将每个能喷洒到草坪边缘的喷水装置的喷洒范围映射成x轴的长度，然后按线段长度递增顺序排列，再从后往前贪心选线段即可看得到选择最少的喷水装置来润湿整个草坪。
代码实现：
package oj;
import java.util.Arrays;
import java.util.Date;
import java.util.Scanner;
/**
* @author Jo
* @create 2020/8/25 17:19
* @description
*/
public class NYOJ06 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for (int i = 0; i < n; i++) {
double[] r = new double[n];
int count = scanner.nextInt(); // 记录总的喷水装置数
for (int j = 0; j < count; j++) {
r[i++] = scanner.nextDouble();
}
// 排序
Arrays.sort(r);
double length = 0;
int num = 0;
for (int j = n - 1; j >= 0; j--) {
length += Math.sqrt(r[j] * r[j] - 1);
num++;
if (length >= 10.0)
break;
}
System.out.println(num);
}
}
}
二、最大不相交区间数问题
问题描述：数轴上有n个区间[ai, bi]，要求选择尽量多个区间，使得这些区间两两没有公共点。
样例：数轴上有7个区间，可选的区间有[2, 6], [1, 4], [3, 6], [3, 7], [6, 8], [2, 4], [3, 5]。
求解过程：
1、按区间右端点递增顺序排列，如果右端点相同，按左端点递增顺序排序，排完序后为[1, 4]，[2, 4], [3, 5], [2, 6], [3, 6], [3, 7], [6, 8]；
2、第一次选择[1, 4]，接下来只能选择[6, 8]，即当前数轴上最多只能选择两个不相同的区间；
3、贪心证明：为了选择更多的区间个数，先按区间右端点递增顺序排列，然后顺序处理每个区间，如果它与当前已选的所有区间都没有相交，则选择该区间，否则不选。接下来证明区间左端点a1，a2…，对右端点没有影响：
①当a1>a2时，区间2包含区间1，显然不能选择区间2，因为选择区间1会留下更多的区域。不仅区间2如此，以后所有区间中只要有一个i满足a1>ai，i都不要选，选择区间1是明智的，与策略一致。
②排除情况1后，一定有a1<=a2<=a3……，此时选择区间1是最优策略，说明无论左端点是大是小，只要对区间右端点进行排序，然后贪心选择不相交的区间就可得到数轴上最多不相交的区间个数，即这个策略是正确的。
题解报告：NYOJ #14会场安排问题
描述：
学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动，每个时间最多安排一个活动。现在小刘有一些活动计划的时间表，他想尽可能的安排更多的活动，请问他该如何安排。
输入：
第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是一个整数n(1
输出：
对于每一组输入，输出最多能够安排的活动数量。
每组的输出占一行
样例输入：
2
2
1 10
10 11
3
1 10
10 11
11 20
样例输出：
1
2
解题思路：按结束时间早进行排序，然后贪心选择不相交区间即可。
示例代码：
import java.util.*;
/**
* @author Jo
* @create 2020/8/25 21:33
* @description
*/
public class NYOJ14 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int time = scanner.nextInt();
for (int i = 0; i < time; i++) {
int n = scanner.nextInt(); // 标志着有几个活动
PriorityQueue<Activity> queue = new PriorityQueue<>();
// 添加活动
for (int j = 0; j < n; j++) {
String[] activities = scanner.nextLine().split(" ");
Activity activity = new Activity(
Integer.parseInt(activities[0]), Integer.parseInt(activities[1]));
queue.add(activity);
}
int count = 1;
int endTime = queue.poll().endTime;
for (int j = 0; j < n; j++) {
if (endTime < queue.peek().beginTime) {
count++;
endTime = queue.peek().endTime;
}
queue.poll(); // 获取并移除此队列的头
}
queue.clear();
System.out.println(count);
}
}
static class Activity implements Comparable<Activity>{
int beginTime, endTime;
Activity(){}
Activity(int beginTime, int endTime) {
this.beginTime = beginTime;
this.endTime = endTime;
}
@Override
public int compareTo(Activity o) {
if (this.endTime > o.endTime) {
return 1;
}
return -1;
}
}
}
三、区间选点问题
问题描述：数轴上有n个闭区间[ai, bi]，要求选取尽量少的点，使得每个区间都至少有一个点（不同区间内含的点可以是同一个）。样例略。
求解过程：
1、按左端点递增顺序排序，如果左端点相同，按右端点递增排序，个人觉得这种比较好理解，当然也可以按右端点递增顺序排序。
2、①从第一个区间右端点开始贪心往后找，如果下一个区间的左端点大于当前已选区间的右端点，说明要新开一点，计数器加1，同时更新右区间能覆盖的最远距离；②如果下一个区间右端点小于当前已选区间的右端点，说明共享的线段范围缩短了，那么就更新区间右端点为下一个区间右端点，重复以上操作，直至筛选完所有区间。
贪心证明：为了选择最少的点使得每个区间内至少含有一个点，考虑按区间左端点递增顺序排序，如果左端点相同，则按区间右端点递增顺序排序，然后以第一个区间右端点作为第一个点能覆盖的最大范围。
①当b1>b2时，显然此时一个点能覆盖最大的区域右边界变为b2，同理，以后只要满足 b1>bib1>bi，一个点能覆盖的区域右边界就会变为 bibi，显然这是正确的；
②当b1<a2时，显然一个点不能覆盖到区间2上，所以需新开一个点，此时能覆盖的区域最右边界变为b2，同理，以后只要满足 b1<aib1<ai，则都要新开一个点，并且其能覆盖的区域右边界将变为 bibi，显然这也是正确的；
③ 当b1<b2时，显然区间1和区间2有公共的部分，但此时一个点能覆盖的区域最右边界还是为 b1，无需更新区域最右边界，同理，对于以后只要满足 b1<bi，都无需新开一个点，也无需更新能覆盖区域的最右边界，显然这也是正确的。综上，按区间左端点递增的顺序排序，再按规则贪心选点的策略是正确的。
题解报告：NYOJ #891 找点
描述：
上数学课时，老师给了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
解题思路：
package oj;
import java.util.Arrays;
import java.util.Scanner;
/**
* @author Jo
* @create 2020/8/25 23:10
* @description
*/
public class NYOJ891 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int n = scanner.nextInt();
Node[] nodes = new Node[n];
for (int i = 0; i < n; i++) {
nodes[i] = new Node(scanner.nextInt(), scanner.nextInt());
}
Arrays.sort(nodes);
boolean[] vis = new boolean[n];
int num = 0;
int loop = 0;
while(num < n) {
Integer min = null, max = null;
for(int i = 0; i<n; i++) {
if(vis[i]) continue;
Node node = nodes[i];
if(min == null) {
min = node.start;
max = node.end;
num ++;
vis[i] = true;
} else {
if(node.start > max) {
break;
}
min = Math.max(min, node.start);
max = Math.min(max, node.end);
vis[i] = true;
num ++;
}
}
loop ++;
}
System.out.println(loop);
}
}
static class Node implements Comparable<Node> {
int start;
int end;
Node(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public int compareTo(Node o) {
int v = this.start - o.start;
if (v != 0) {
return v;
}
return o.end - this.end;
}
}
}
代码没具体校验过，后期继续。
若有收获，就点个赞吧
0 人点赞
