蓝桥每日打卡--区间移位

#蓝桥#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();// 读取每个区间的右端点，并将其乘以 2intervals[i][1] = 2 * scan.nextInt();}scan.close();// 对 intervals 数组按照每个区间的右端点进行排序，使用 Comparator.comparingInt 方法指定排序规则Arrays.sort(intervals, Comparator.comparingInt(i -> i[1]));// 初始化二分查找的左边界为 0int left = 0;// 初始化二分查找的右边界为 20000，这里假设最大的位移量不会超过 20000int 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) {// 初始化覆盖范围为 0int cover = 0;// 创建一个 ArrayList 并将 intervals 数组中的元素复制到其中，方便后续的删除操作List<int[]> temp = new ArrayList<>(Arrays.asList(intervals)); // 进入一个无限循环，用于逐个处理区间while (true) {// 标记是否有合格的区间，初始化为 falseboolean 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，否则返回 falsereturn cover >= 2e4;}
}