当前位置：首页 > news >正文

蓝桥杯之二分法(二)

news 来源：原创 2025/8/21 21:23:07

存在某条件使得一边均满足，一边均不满足：
如果问题满足某种条件，使得在某个点之前的所有值都满足条件，而之后的所有值都不满足条件（或反之），那么可以使用二分法来找到这个边界。

1.问题的解具有单调性

这是使用二分法的核心条件。单调性可以理解为：

如果某个值 x 满足条件，那么所有小于 x 的值也必然满足条件。
如果某个值 x 不满足条件，那么所有大于 x 的值也必然不满足条件。

2.问题的典型问法

最大化在满足某条件下的解值：例如“求某个最大值的最小值”。
最小化在满足某条件下的解值：例如“求某个最小值的最大值”。
求某个变量的最大值或最小值：例如“求最小的 x 使得某个条件成立”

3.相关的题目练习

冶炼金属

问题描述

小蓝有一个神奇的炉子用于将普通金属 OO 冶炼成为一种特殊金属 XX。这个炉子有一个称作转换率的属性 VV，VV 是一个正整数，这意味着消耗 VV 个普通金属 OO 恰好可以冶炼出一个特殊金属 XX，当普通金属 OO 的数目不足 VV 时，无法继续冶炼。

现在给出了 NN 条冶炼记录，每条记录中包含两个整数 AA 和 BB，这表示本次投入了 AA 个普通金属 OO，最终冶炼出了 BB 个特殊金属 XX。每条记录都是独立的，这意味着上一次没消耗完的普通金属 OO 不会累加到下一次的冶炼当中。

根据这 NN 条冶炼记录，请你推测出转换率 VV 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。

输入格式

第一行一个整数 NN，表示冶炼记录的数目。

接下来输入 NN 行，每行两个整数 AA、BB，含义如题目所述。

输出格式

输出两个整数，分别表示 VV 可能的最小值和最大值，中间用空格分开。

样例输入

样例输出

20 25

样例说明

当 V=20V=20 时，有：⌊7520⌋=3⌊2075⌋=3，⌊5320⌋=2⌊2053⌋=2，⌊5920⌋=2⌊2059⌋=2，可以看到符合所有冶炼记录。

当 V=25V=25 时，有：⌊7525⌋=3⌊2575⌋=3，⌊5325⌋=2⌊2553⌋=2，⌊5925⌋=2⌊2559⌋=2，可以看到符合所有冶炼记录。

且再也找不到比 2020 更小或者比 2525 更大的符合条件的 VV 值了。

import java.util.*;
public class Main {static int A = 0; // 可能是未使用的变量static int B = 0; // 可能是未使用的变量static int n = 0; // 输入的数组长度static final int N = 10040; // 定义数组的最大长度static int[] a = new int[N]; // 存储每个元素的值static int[] sum = new int[N]; // 存储每个元素对应的条件值static int ans1 = 0; // 存储最大值的结果static int ans2 = 0; // 存储最小值的结果// 求最大值的 check 函数public static boolean check1(int x) {for (int i = 1; i <= n; i++) {// 判断 a[i] / x 是否大于等于 sum[i]if (a[i] / x < sum[i]) {return false; // 如果不满足条件，返回 false}}return true; // 如果所有条件都满足，返回 true}// 求最小值的 check 函数public static boolean check2(int x) {for (int i = 1; i <= n; i++) {// 判断 a[i] / x 是否小于等于 sum[i]if (a[i] / x > sum[i]) {return false; // 如果不满足条件，返回 false}}return true; // 如果所有条件都满足，返回 true}public static void main(String[] args) {Scanner scan = new Scanner(System.in);n = scan.nextInt(); // 读取数组长度for (int i = 1; i <= n; i++) {a[i] = scan.nextInt(); // 读取每个元素的值sum[i] = scan.nextInt(); // 读取每个元素对应的条件值}// 寻找最大值int l = 1; // 初始化左边界int r = 1000000000; // 初始化右边界（一个很大的数）while (r > l) {int mid = (r + l + 1) >> 1; // 计算中间值if (check1(mid)) {// 如果满足条件，尝试更大的值l = mid;} else {// 如果不满足条件，尝试更小的值r = mid - 1;}ans1 = l; // 更新最大值结果}// 寻找最小值l = 1; // 重置左边界r = 1000000000; // 重置右边界while (r > l) {int mid = (r + l) >> 1; // 计算中间值if (check2(mid)) {// 如果满足条件，尝试更小的值r = mid;} else {// 如果不满足条件，尝试更大的值l = mid + 1;}ans2 = r; // 更新最小值结果}// 输出结果System.out.print(ans2); // 输出最小值System.out.print(" ");System.out.print(ans1); // 输出最大值scan.close();}
}

二分查找的关键技巧

确保单调性
- 二分查找适用于具有单调性的场景。例如：
  - 数组是有序的。
  - 条件满足时，所有左边的值都满足，右边的都不满足（或反之）。
定义左右边界
- 左边界：问题的最小可能值（通常是 1 或 0）。
- 右边界：问题的最大可能值（可以设置一个足够大的值）。
设计 check 函数
- check 函数是核心，用于判断中间值是否满足条件。
- 返回 true 表示条件满足，可以尝试更大的值；返回 false 表示条件不满足，需要尝试更小的值。
中间值的计算
- 使用 mid = (l + r) >> 1（向下取整）或 mid = (l + r + 1) >> 1（向上取整），根据问题需求选择合适的计算方式。
更新边界
- 如果 check(mid) 为 true，更新左边界：l = mid。
- 如果 check(mid) 为 false，更新右边界：r = mid - 1。
循环条件
- 使用 while (l < r) 作为循环条件，直到找到答案。
输出结果
- 循环结束后，l 或 r 即为答案。

1.问题的解具有单调性

2.问题的典型问法

3.相关的题目练习

冶炼金属

二分查找的关键技巧

相关文章：