二分答案相关题目

二分答案

珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

示例 1：
输入：piles = [3,6,7,11], h = 8
输出：4

思路：二分答案。先将数组大到小排序，取最小速度0和最大速度为piles[n - 1]，作为速度的左右边界，然后使用二分法，缩小速度的区间，直到找到最小的速度。

代码：

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int n = piles.length;
        Arrays.sort(piles);
        if (h == n) return piles[n - 1];
        int left = 0, right = piles[n - 1];
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            int hours = 0;
          	// 遍历整个数组，求出在当前速度下吃完要多少小时
            for (int i = 0; i < n; ++i) {
                hours += Math.ceil(piles[i] * 1.0 / mid);
            }
            if (hours <= h) right = mid; // h小时内能吃完,速度够，修改速度右边界为mid
            else left = mid + 1; // h小时内不能吃完，速度小了，修改速度左边界为mid + 1
        }
        return left;
    }
}

时间复杂度：O(NlogM)，n为数组piles长度，m为piles的最大值。二分查找执行O(logm)轮，每一轮需要O(n)时间求出每个速度下吃完需要的时间。

力扣2616：最小化数对的最大差值

给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对，每个下标对对应数值取差值，你需要使得这 p 个差值的 最大值最小。同时，你需要确保每个下标在这 p 个下标对中最多出现一次。对于一个下标对 i 和 j ，这一对的差值为 |nums[i] - nums[j]| ，其中 |x| 表示 x 的绝对值。请你返回 p 个下标对对应数值 最大差值 的 最小值 。

示例 1：
输入：nums = [10,1,2,7,1,3], p = 2
输出：1
解释：第一个下标对选择 1 和 4 ，第二个下标对选择 2 和 5 。
最大差值为 max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1 。所以我们返回 1 。

思路：同上一题，使用二分答案方法。看到最小化最大值或者最大化最小值首先想到要用二分法。

代码：

class Solution {
    public int minimizeMax(int[] nums, int p) {
        Arrays.sort(nums); // 先排序
        int n = nums.length, left = 0, right = nums[n - 1] - nums[0];  // 定义最大差值的左右边界
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            int count = 0;
            // 遍历整个数组，看看有多少对满足差值小于mid的数对
            for (int i = 0; i < n - 1; ++i) {
                if (nums[i + 1] - nums[i] <= mid) {
                    ++count;
                    ++i;
                }
            }
            if (count >= p) right = mid; // 可以找到p对差值小于mid，修改右边界为mid
            else left = mid + 1; // 不能找到p对，说明mid值太小了，左边界换成mid + 1
        }
        return left;
    }
}

时间复杂度：O(NlogC)，C为二分查找的上下限之差

其他相关题目：

补充：华为4.12暑期实习机考第一题

交易系统的降级策略:

有一个核心交易系统接口被N个上游系统调用，每个上游系统的调用量R=[R1,R2…..,RN].由于核心交易系统集群故障，需要暂时系统降级限制调用，核心交易系统能接受的最大调用量为cnt。设置降级规则如下;如果sum(R1.R2..RN)小于等于cnt，则全部可以正常调用，返回-1;如果sum(R1.R2….RN)大于cnt，设置一个阈值limit，如果某个上游系统发起的调用量超过limit，就将该上游系统的调用量限制为limit，其余未达到limit的系统可以正常发起调用。求出这个最大的lmit (mit可以为0)此题目对效率有要求，请选择高效的方式。

输入描述：
第一行:每个上游系统的调用量(整型数组)
第二行:核心交易系统的最大调用量 0<R.length<=10^5，0<R[i]<10^5，0<cnt <= 10^9

输出描述：
调用量的阈值Iimit

示例：

输入：
1 4 2 5 5 1 6
13
输出：
2
解释：因为1+4+2+5+5+1+6>13;将limit设置为2，则1+2+2+2+2+1+2=12<13。所以imit为2

输入：
1 7 8 8 1 0 2 4 9
7
输出：
0
解释：因为即使imil设置为1,1+1+1+1+1+1+1+1=8>7也不满足，所以limit只能为0

思路：题目意思就是设置一个阈值limit，把数组中大于limit的元素的值改为limit，小于limit的元素值不变，使得最终数组的元素和不超过cnt。使用二分答案法。

代码：

import java.util.*;
public class Solution {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        String[] input = cin.nextLine().split(" ");
        int n = input.length;
        int[] arr = new int[n];
        long s = 0;
        for (int i = 0; i < n; ++i) {
            arr[i] = Integer.parseInt(input[i]);
            s += arr[i];
        }
        int cnt = cin.nextInt();
        if (s <= cnt) {
            System.out.println(-1);
            return;
        }
        int left = 0, right = 100000;
        while (left < right) {
            int mid = (left + right + 1) / 2; // 阈值设为mid
            long sum = 0;
            // 求和
            for (int i = 0; i < n; ++i) {
                if (arr[i] <= mid) {
                    sum += arr[i];
                } else {
                    sum += mid;
                }
            }
            // 满足条件
            if (sum <= cnt) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        System.out.println(left);
    }
}