算法【二分答案法】

本文需掌握二分搜索。

二分答案法

1.估计最终答案可能的范围是什么，可以定的粗略，反正二分不了几次。

2.分析问题的答案和给定条件之间的单调性，大部分时候只需要用到自然智慧。

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

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

核心点：分析单调性、建立f函数

下面通过几个题目加深理解。

题目一

测试链接：https://leetcode.cn/problems/koko-eating-bananas/

分析：可以通过题目得到答案的大致范围，通过对答案范围的二分搜索，将每次搜索的答案进行判定，该答案是否合法。搜索完毕即可得到最优的答案。代码如下。

class Solution {
public:bool f(vector<int>& piles, int h, int k){long long hours = 0;int length = piles.size();for(int i = 0;i < length;++i){hours += ((piles[i] + k - 1) / k);}return hours <= h;}int minEatingSpeed(vector<int>& piles, int h) {long long ans;int left = 1;int right = *(max_element(piles.begin(), piles.end()));int middle;while (left <= right){middle = left + ((right - left) >> 1);if(f(piles, h, middle)){right = middle - 1;ans = middle;}else{left = middle + 1;}}return ans;}
};

其中，left和right分别是答案范围的左边界和右边界。f方法返回以k速度吃香蕉是否能在h小时内吃完。

题目二

测试链接：https://leetcode.cn/problems/split-array-largest-sum/

分析：二分答案法思路都差不多，主要是f函数的意义，范围的设置等，后面的题目不再赘述。代码如下。

class Solution {
public:bool f(vector<int>& nums, int he, int k){int group = 0;int sum = 0;for(int i = 0;i < nums.size();++i){if(nums[i] > he){return false;}if(sum + nums[i] > he){sum = nums[i];++group;}else{sum += nums[i];}}return (group + 1) <= k;}int splitArray(vector<int>& nums, int k) {int ans;int left = 0;int right = accumulate(nums.begin(), nums.end(), 0);int middle;while (left <= right){middle = left + ((right - left) >> 1);if(f(nums, middle, k)){right = middle - 1;ans = middle;}else{left = middle + 1;}}return ans;}
};

其中，f方法返回的是将nums数组分为和不超过he的子数组的个数是否小于等于k。

题目三

测试链接：https://www.nowcoder.com/practice/7037a3d57bbd4336856b8e16a9cafd71

分析：代码如下。

#include <iostream>
#include <vector>
using namespace std;
int N;
int max_value;
vector <int> H;
bool f(int E){for(int i = 0;i < N;++i){E += (E - H[i]);if(E >= max_value){return true;}if(E < 0){return false;}}return true;
}
int main(void){int ans;int left = 0;int right = 0;int middle;scanf("%d", &N);H.assign(N, 0);for(int i = 0;i < N;++i){scanf("%d", &H[i]);right = right > H[i] ? right : H[i];}max_value = right;while (left <= right){middle = left + ((right - left) >> 1);if(f(middle)){right = middle - 1;ans = middle;}else{left = middle + 1;}}printf("%d", ans);
}

其中，f函数返回以E能量值出发能否到终点。

题目四

测试链接：https://leetcode.cn/problems/find-k-th-smallest-pair-distance/

分析：代码如下。

class Solution {
public:bool f(vector<int>& nums, int k, int value, int length){int num = 0;for(int left = 0, right = 1;left < length && right < length;++right){if(nums[right] - nums[left] < value){num += (right - left);}else{while (nums[right] - nums[left] >= value && left < right){++left;}num += (right - left);}}return num >= k;}int smallestDistancePair(vector<int>& nums, int k) {sort(nums.begin(), nums.end());int length = nums.size();int ans;int left = 0;int right = nums[length-1] - nums[0];int middle;while (left <= right){middle = left + ((right - left) >> 1);if(f(nums, k, middle, length)){right = middle - 1;}else{left = middle + 1;ans = middle;}}return ans;}
};

其中，f方法返回在nums数组中比value小的数对的个数是否大于等于k，通过nums数组中比value小的数对的个数采用滑动窗口求解。

题目五

测试链接：https://leetcode.cn/problems/maximum-running-time-of-n-computers/

分析：代码如下。

class Solution {
public:bool f(vector<int>& batteries, int n, long long minutes, int index){int num = 0;while (index - num >= 0 && batteries[index-num] > minutes){++num;}n -= num;index -= num;long long sum = 0;for(int i = 0;i <= index;++i){sum += batteries[i];}return sum >= (long long)n * (long long)minutes;}long long maxRunTime(int n, vector<int>& batteries) {long long ans;long long left = 0;long long right = accumulate(batteries.begin(), batteries.end(), (long long)0);long long middle;int length = batteries.size();sort(batteries.begin(), batteries.end());while (left <= right){middle = left + ((right - left) >> 1);if(f(batteries, n, middle, length-1)){ans = middle;left = middle + 1;}else{right = middle - 1;}}return ans;}
};

其中，f方法返回n台电脑能够同时运行minutes分钟。

采用这种思路，速度较慢，可以加入一个贪心优化一下。代码如下。

class Solution {
public:bool f(vector<int>& batteries, int n, long long minutes, int length){long long sum = 0;for(int i = 0;i < length;++i){if(batteries[i] > minutes){--n;}else{sum += batteries[i];}if(sum >= (long long)n * (long long)minutes){return true;}}return false;}long long maxRunTime(int n, vector<int>& batteries) {long long ans;long long left = 0;long long right;long long middle;long long sum = 0;int max_value = 0;int length = batteries.size();for(int i = 0;i < length;++i){sum += batteries[i];max_value = max_value > batteries[i] ? max_value : batteries[i];}right = sum;if(sum >= (long long)max_value * (long long)n){return sum / n;}while (left <= right){middle = left + ((right - left) >> 1);if(f(batteries, n, middle, length)){ans = middle;left = middle + 1;}else{right = middle - 1;}}return ans;}
};

加入了如果数组的和大于等于数组最大值与电脑台数的乘积，则直接返回数组和除以电脑台数即是答案的判断。其他部分，与之前思路一样，改变一些写法。

题目六

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

谷歌的面试，这个题连考了2个月。

分析：代码如下。

class Solution {
public:bool f(vector<int>& arr, int m, int minutes, int length){int sum = 0;for(int i = 0;i < length;++i){sum += ((minutes + arr[i] - 1)/ arr[i]);}return sum >= m+1;}int WaitTime(vector<int>& arr, int m) {int ans;int length = arr.size();int left = 0;int right = *(min_element(arr.begin(), arr.end()));int middle;while (left <= right){middle = left + ((right - left) >> 1);if(f(arr, m, middle, length)){right = middle - 1;ans = middle;}else{left = middle + 1;}}return ans;}
};

其中，f方法返回minutes分钟能不能服务到自己。

题目七

题目描述：

刀砍毒杀怪兽问题。怪兽的初始血量是一个整数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

真实大厂算法笔试题。

分析：代码如下。

class Solution {
public:bool f(int hp, vector<int>& cuts, vector<int>& poisons, int round, int length){for(int i = 0;i < length && i < round;++i){if(cuts[i] >= (round - i - 1) * poisons[i]){hp -= cuts[i];}else{hp -= ((round - i - 1) * poisons[i]);}if(hp <= 0){return true;}}return false;}int ShortestRound(int hp, vector<int>& cuts, vector<int>& poisons) {int ans;int length = cuts.size();int left = 1;int right = hp+1;int middle;while (left <= right){middle = left + ((right - left) >> 1);if(f(hp, cuts, poisons, middle, length)){right = middle - 1;ans = middle;}else{left = middle + 1;}}return ans;}
};

其中，f方法返回在round回合能否杀死boss。