蓝桥每日打卡--区间移位
#蓝桥#JAVA#区间移位
题目描述
数轴上有n个闭区间：D1,⋯Dn。
其中区间Di用一对整数[ai,bi]来描述，满足 ai≤bi。
已知这些区间的长度之和至少有。
所以，通过适当的移动这些区间，你总可以使得他们的"并"覆盖 [0,],也就是说 [0,
]这个区间内的每一个点都落于至少一个区间内。
你希望找一个移动方法，使得位移差最大的那个区间的位移量最小。
具体来说，假设你将Di移动到 [ai+ci,bi+ci]这个位置。你希望使得max∣ci∣最小。
解题思路
首先这道题可以参考蓝桥每日打卡--打家劫舍4-CSDN博客这个最小化最大值的思路
①选取数组不相邻元素 ②限选≥k≥k个 ③求最大值（单个方案中能偷最多的）中的最小值（所有方案汇聚而成的可行域中的最小值）
触发条件：看到最大化最小值或最小化最大值，就要想到二分答案，这是固定套路
- 本题的二分指的是答案的二分——虽然
nums不是单调的，但答案的取值范围是单调的，可以二分查找区间的最小值
区间 [0, max_element]：
| 不满足条件的区间 | 单次能偷的最大值范围（答案所在区间） |
↑
要找的在这里
check函数：判断单次窃取上限为maxL时，能否偷满至少k个minCapability函数：对答案所在区间进行二分查找- 因为答案分布在所有可能的结果中，所以将左指针初始化为
0，右指针初始化为数组最大值 - 要找的是答案所在区间的最小值
- 因为答案分布在所有可能的结果中，所以将左指针初始化为
贪心+二分查找
int minCapability(int[] nums, int k) {
int left = 0, right = Integer.MIN_VALUE;
for (int num : nums) right = Math.max(right, num);
while (left < right) {
int mid = (left + right) >> 1;
if (check(nums, mid, k)) right = mid;
else left = mid + 1;
}
return right;
}
boolean check(int[] nums, int cap, int k) {
int count = 0;
for (int i = 0; i < nums.length; ++i) {
if (nums[i] <= cap) {
++count;
++i; // 跳过相邻的
}
}
return count >= k;
}
import java.util.*;
public class Main {
// 定义一个二维数组 intervals，用于存储输入的区间信息
private static int[][] intervals;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
intervals = new int[n][2];
for (int i = 0; i < n; ++i) {
// 读取每个区间的左端点，并将其乘以 2，这样做是为了方便后续计算，避免在计算位移量时进行除法操作
intervals[i][0] = 2 * scan.nextInt();
// 读取每个区间的右端点，并将其乘以 2
intervals[i][1] = 2 * scan.nextInt();
}
scan.close();
// 对 intervals 数组按照每个区间的右端点进行排序，使用 Comparator.comparingInt 方法指定排序规则
Arrays.sort(intervals, Comparator.comparingInt(i -> i[1]));
// 初始化二分查找的左边界为 0
int left = 0;
// 初始化二分查找的右边界为 20000，这里假设最大的位移量不会超过 20000
int right = (int) 2e4;
// 开始二分查找，使用左闭右开区间的二分查找模板
while (left < right) {
// 计算中间值 mid，使用位运算 >> 1 代替除以 2，提高计算效率
int mid = (left + right) >> 1;
// 调用 check 方法检查当前位移量 mid 是否满足条件
if (check(mid))
// 如果满足条件，说明 mid 可能是一个可行解，将右边界更新为 mid，缩小查找范围
right = mid;
else
// 如果不满足条件，说明 mid 太小，将左边界更新为 mid + 1，扩大查找范围
left = mid + 1;
}
// 判断最终结果是否为偶数
if (right % 2 == 0)
// 如果是偶数，直接将结果除以 2 并输出
System.out.println(right / 2);
else
// 如果是奇数，将结果转换为 double 类型后除以 2 并输出
System.out.println((double) right / 2);
}
// 定义 check 方法，用于检查给定的位移量 shift 是否能使所有区间覆盖到指定范围
private static boolean check(int shift) {
// 初始化覆盖范围为 0
int cover = 0;
// 创建一个 ArrayList 并将 intervals 数组中的元素复制到其中，方便后续的删除操作
List<int[]> temp = new ArrayList<>(Arrays.asList(intervals));
// 进入一个无限循环，用于逐个处理区间
while (true) {
// 标记是否有合格的区间，初始化为 false
boolean qualified = false;
// 遍历 temp 列表中的每个区间
for (int i = 0; i < temp.size(); ++i) {
// 获取当前区间
int[] interval = temp.get(i);
// 检查当前区间向左移动 shift 后是否能连接到前面的覆盖范围，并且向右移动 shift 后不超过最大范围
if (interval[0] - shift <= cover && interval[1] + shift >= cover) {
// 如果满足条件，标记有合格的区间
qualified = true;
// 计算当前区间的长度
int len = interval[1] - interval[0];
// 如果当前区间左移后超过前面区间的覆盖范围，那么此次移动，覆盖范围最多只能增加当前区间本身的长度
if (interval[0] + shift >= cover)
cover += len;
else
// 若不能超过，覆盖范围最多是当前区间末端 + 位移量
cover = interval[1] + shift;
// 从 temp 列表中移除当前区间
temp.remove(i);
// 跳出当前 for 循环，避免 ConcurrentModificationException 异常
break;
}
}
// 如果没有合格的区间或者覆盖范围已经达到 20000，跳出无限循环
if (!qualified || cover >= 2e4) break;
}
// 判断最终的覆盖范围是否达到 20000，如果达到则返回 true，否则返回 false
return cover >= 2e4;
}
}