二分答案法
-
估计最终答案的大概范围
-
分析问题的答案和给定条件之间的单调性
-
建立一个 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 / num
return 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;
}
}