二分答案法

二分答案法

• 估计最终答案的大概范围

• 分析问题的答案和给定条件之间的单调性

• 建立一个 f 函数，当答案固定的情况下，判断给定的条件是否达标

• 在最终答案可能的范围上不断二分搜索，每次用 f 函数判断，直到二分结束，找到最合适的答案

875. 爱吃香蕉的珂珂

#include <vector>
#include <algorithm>using namespace std;class Solution {
public:// 返回要消耗的时间long timeConsuming(vector<int> &piles, int k) {long res = 0;for (const auto &item: piles)// item / k 向上取整，前提都是非负数res += (item + k - 1) / k;return res;}// 时间复杂度 O(n * log(max))，额外空间复杂度 O(1)int minEatingSpeed(vector<int> &piles, int h) {int left = 1;int right = 0;for (const auto &item: piles)right = max(right, item);int mid;while (left <= right) {mid = left + ((right - left) >> 1);if (timeConsuming(piles, mid) <= h) {right = mid - 1;} else {left = mid + 1;}}return left;}
};

410. 分割数组的最大值

画匠问题：

• 一维数组表示每个位置的画完成需要的时间，k 表示画匠人数
• 每个画匠可以画连续的几幅画，画匠可以并行工作，求最小耗时
• 其实就是把数组分成连续的 k 个子数组，使得所有子数组中和最大的那个的和尽量小

#include <vector>
#include <algorithm>using namespace std;class Solution {
public:// 每个连续部分的和不超过 limit 的情况下，需要多少个画匠完成全部画作int painterNeeded(vector<int> &nums, int limit) {int count = 1;int sum = 0;// 时间复杂度 O(n)for (const auto &num: nums) {// 表示完成不了if (num > limit) return INT_MAX;if (sum + num > limit) {count++;sum = num;} else {sum += num;}}return count;}// 时间复杂度 O(n * log(sum))，额外空间复杂度 O(1)int splitArray(vector<int> &nums, int k) {long left = 0;long right = 0;for (const auto &item: nums)right += item;long mid;while (left <= right) {mid = left + ((right - left) >> 1);if (painterNeeded(nums, mid) <= k) {right = mid - 1;} else {left = mid + 1;}}return left;}
};

机器人跳跃问题

#include <vector>
#include <iostream>
#include <algorithm>using namespace std;// 以初始能量 energy 能否走完数组
bool finished(vector<int> &nums, int energy, int maxH) {for (const auto &item: nums) {energy += (energy - item);// 如果超过高度最大值，后面肯定通关了，可以提前返回if (energy >= maxH) return true;if (energy < 0) return false;}return true;
}// 时间复杂度 O(n * log(maxH))，额外空间复杂度 O(1)
int main() {int n;cin >> n;vector<int> nums(n);int maxH = 0;for (int i = 0; i < n; ++i) {cin >> nums[i];maxH = max(maxH, nums[i]);}int left = 0;int right = maxH;int mid;while (left <= right) {mid = left + ((right - left) >> 1);if (finished(nums, mid, maxH)) {right = mid - 1;} else {left = mid + 1;}}cout << left;
}

719. 找出第 K 小的数对距离

#include <vector>
#include <algorithm>using namespace std;class Solution {
public:// 返回任意两数差值小于等于 limit 的数对个数int countLower(vector<int> &nums, int limit) {int count = 0;for (int l = 0, r = 0; l < nums.size(); ++l) {while (r + 1 < nums.size() && nums[r + 1] - nums[l] <= limit)r++;count += r - l;}return count;}// 时间复杂度 O(n * log(n) + n * log(max-min))，额外空间复杂度 O(1)int smallestDistancePair(vector<int> &nums, int k) {sort(nums.begin(), nums.end());int left = 0;int right = nums.back() - nums.front();int mid;while (left <= right) {mid = left + ((right - left) >> 1);if (countLower(nums, mid) >= k) {right = mid - 1;} else {left = mid + 1;}}return left;}
};

2141. 同时运行 N 台电脑的最长时间

#include <vector>using namespace std;class Solution {
public:// 能否让 computers 台电脑共同运行 time 分钟bool finished(vector<int> &batteries, int computers, long time) {// 碎片电量总和long fragmentCharge = 0;for (const auto &charge: batteries) {if (charge > time) {// time 时间内全都给这台电脑供电，没有提供碎片电量computers--;} else {// 碎片电量fragmentCharge += charge;}// 碎片电量 >= 台数 * 要求if (fragmentCharge >= (long) computers * time) return true;}return false;}// 时间复杂度 O(n * log(sum))，额外空间复杂度 O(1)long long maxRunTime(int n, vector<int> &batteries) {long sum = 0;for (const auto &item: batteries)sum += item;long left = 0;long right = sum;long mid;while (left <= right) {mid = left + ((right - left) >> 1);if (finished(batteries, n, mid)) {left = mid + 1;} else {right = mid - 1;}}return right;}
};

• 贪心优化

#include <vector>using namespace std;class Solution {
public:// 能否让 computers 台电脑共同运行 time 分钟bool finished(vector<int> &batteries, int computers, long time) {// 碎片电量总和long fragmentCharge = 0;for (const auto &charge: batteries) {if (charge > time) {// time 时间内全都给这台电脑供电，没有提供碎片电量computers--;} else {// 碎片电量fragmentCharge += charge;}// 碎片电量 >= 台数 * 要求if (fragmentCharge >= (long) computers * time) return true;}return false;}// 时间复杂度 O(n * log(_max))，额外空间复杂度 O(1)long long maxRunTime(int n, vector<int> &batteries) {long sum = 0;int _max = 0;for (const auto &item: batteries) {sum += item;_max = max(_max, item);}// 优化if (sum > (long) _max * n) {// 所有电池的最大电量是 _max// 如果此时 sum > (long) _max * num，// 说明: 最终的供电时间一定在 >= max，而如果最终的供电时间 >= max// 说明: 对于最终的答案 X 来说，所有电池都是碎片电池// 那么寻找 ? * num <= sum 的情况中，尽量大的 ? 即可// 即 sum / numreturn sum / n;}// 最终的供电时间一定在 < _max 范围上long left = 0;long right = _max;long mid;while (left <= right) {mid = left + ((right - left) >> 1);if (finished(batteries, n, mid)) {left = mid + 1;} else {right = mid - 1;}}return right;}
};

计算等位时间

• 给定一个数组 arr 长度为 n，表示 n 个服务员，每服务一个人的时间
• 给定一个正数 m，表示有 m 个人等位，如果你是刚来的人，每个客人都遵循有空位就上的原则，请问你需要等多久？
• 假设 m 远远大于 n，比如 n <= 10^3, m <= 10^9，该怎么做是最优解？

package class051;import java.util.PriorityQueue;// 计算等位时间
// 给定一个数组arr长度为n，表示n个服务员，每服务一个人的时间
// 给定一个正数m，表示有m个人等位，如果你是刚来的人，请问你需要等多久？
// 假设m远远大于n，比如n <= 10^3, m <= 10^9，该怎么做是最优解？
// 谷歌的面试，这个题连考了2个月
// 找不到测试链接，所以用对数器验证
public class Code06_WaitingTime {// 堆模拟// 验证方法，不是重点// 如果m很大，该方法会超时// 时间复杂度O(m * log(n))，额外空间复杂度O(n)public static int waitingTime1(int[] arr, int m) {// 一个一个对象int[]// [醒来时间，服务一个客人要多久]PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> (a[0] - b[0]));int n = arr.length;for (int i = 0; i < n; i++) {heap.add(new int[]{0, arr[i]});}for (int i = 0; i < m; i++) {int[] cur = heap.poll();cur[0] += cur[1];heap.add(cur);}return heap.peek()[0];}// 二分答案法// 最优解// 时间复杂度O(n * log(min * w))，额外空间复杂度O(1)public static int waitingTime2(int[] arr, int w) {int min = Integer.MAX_VALUE;for (int x : arr) {min = Math.min(min, x);}int ans = 0;for (int l = 0, r = min * w, m; l <= r; ) {// m中点，表示一定要让服务员工作的时间！m = l + ((r - l) >> 1);// 能够给几个客人提供服务if (f(arr, m) >= w + 1) {ans = m;r = m - 1;} else {l = m + 1;}}return ans;}// 如果每个服务员工作time，可以接待几位客人（结束的、开始的客人都算）public static int f(int[] arr, int time) {int ans = 0;for (int num : arr) {ans += (time / num) + 1;}return ans;}// 对数器测试public static void main(String[] args) {System.out.println("测试开始");int N = 50;int V = 30;int M = 3000;int testTime = 20000;for (int i = 0; i < testTime; i++) {int n = (int) (Math.random() * N) + 1;int[] arr = randomArray(n, V);int m = (int) (Math.random() * M);int ans1 = waitingTime1(arr, m);int ans2 = waitingTime2(arr, m);if (ans1 != ans2) {System.out.println("出错了!");}}System.out.println("测试结束");}// 对数器测试public static int[] randomArray(int n, int v) {int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = (int) (Math.random() * v) + 1;}return arr;}}

刀砍毒杀怪兽问题

package class051;// 刀砍毒杀怪兽问题
// 怪兽的初始血量是一个整数hp，给出每一回合刀砍和毒杀的数值cuts和poisons
// 第i回合如果用刀砍，怪兽在这回合会直接损失cuts[i]的血，不再有后续效果
// 第i回合如果用毒杀，怪兽在这回合不会损失血量，但是之后每回合都损失poisons[i]的血量
// 并且你选择的所有毒杀效果，在之后的回合都会叠加
// 两个数组cuts、poisons，长度都是n，代表你一共可以进行n回合
// 每一回合你只能选择刀砍或者毒杀中的一个动作
// 如果你在n个回合内没有直接杀死怪兽，意味着你已经无法有新的行动了
// 但是怪兽如果有中毒效果的话，那么怪兽依然会在血量耗尽的那回合死掉
// 返回至少多少回合，怪兽会死掉
// 数据范围 : 
// 1 <= n <= 10^5
// 1 <= hp <= 10^9
// 1 <= cuts[i]、poisons[i] <= 10^9
// 本题来自真实大厂笔试，找不到测试链接，所以用对数器验证
public class Code07_CutOrPoison {// 动态规划方法(只是为了验证)// 目前没有讲动态规划，所以不需要理解这个函数// 这个函数只是为了验证二分答案的方法是否正确的// 纯粹为了写对数器验证才设计的方法，血量比较大的时候会超时// 这个方法不做要求，此时并不需要理解，可以在学习完动态规划章节之后来看看这个函数public static int fast1(int[] cuts, int[] poisons, int hp) {int sum = 0;for (int num : poisons) {sum += num;}int[][][] dp = new int[cuts.length][hp + 1][sum + 1];return f1(cuts, poisons, 0, hp, 0, dp);}// 不做要求public static int f1(int[] cuts, int[] poisons, int i, int r, int p, int[][][] dp) {r -= p;if (r <= 0) {return i + 1;}if (i == cuts.length) {if (p == 0) {return Integer.MAX_VALUE;} else {return cuts.length + 1 + (r + p - 1) / p;}}if (dp[i][r][p] != 0) {return dp[i][r][p];}int p1 = r <= cuts[i] ? (i + 1) : f1(cuts, poisons, i + 1, r - cuts[i], p, dp);int p2 = f1(cuts, poisons, i + 1, r, p + poisons[i], dp);int ans = Math.min(p1, p2);dp[i][r][p] = ans;return ans;}// 二分答案法// 最优解// 时间复杂度O(n * log(hp))，额外空间复杂度O(1)public static int fast2(int[] cuts, int[] poisons, int hp) {int ans = Integer.MAX_VALUE;for (int l = 1, r = hp + 1, m; l <= r;) {// m中点，一定要让怪兽在m回合内死掉，更多回合无意义m = l + ((r - l) >> 1);if (f(cuts, poisons, hp, m)) {ans = m;r = m - 1;} else {l = m + 1;}}return ans;}// cuts、posions，每一回合刀砍、毒杀的效果// hp：怪兽血量// limit：回合的限制public static boolean f(int[] cuts, int[] posions, long hp, int limit) {int n = Math.min(cuts.length, limit);for (int i = 0, j = 1; i < n; i++, j++) {hp -= Math.max((long) cuts[i], (long) (limit - j) * (long) posions[i]);if (hp <= 0) {return true;}}return false;}// 对数器测试public static void main(String[] args) {// 随机测试的数据量不大// 因为数据量大了，fast1方法会超时// 所以在数据量不大的情况下，验证fast2方法功能正确即可// fast2方法在大数据量的情况下一定也能通过// 因为时间复杂度就是最优的System.out.println("测试开始");int N = 30;int V = 20;int H = 300;int testTimes = 10000;for (int i = 0; i < testTimes; i++) {int n = (int) (Math.random() * N) + 1;int[] cuts = randomArray(n, V);int[] posions = randomArray(n, V);int hp = (int) (Math.random() * H) + 1;int ans1 = fast1(cuts, posions, hp);int ans2 = fast2(cuts, posions, hp);if (ans1 != ans2) {System.out.println("出错了!");}}System.out.println("测试结束");}// 对数器测试public static int[] randomArray(int n, int v) {int[] ans = new int[n];for (int i = 0; i < n; i++) {ans[i] = (int) (Math.random() * v) + 1;}return ans;}}