用二分法，在一个范围内取中间数看有没有满足求 最大值 的条件（因为是先求最大值，再在最大值中求最小值），一次二分可以否定掉一半的范围，一次次缩减范围，锁定我们要求的数。
假设我们要求的最小 最大值是res。m是二分的中间值，范围[l, r] 范围是开区间还是闭区间要视具体情况而定，这里举例子用的闭区间
- m满足条件：范围变成[l, m]，m满足条件，比m大的就都可以否定了(因为是求最小值，所以后面的数就算满足条件但是比m大 也不会是我们要求的最小值)，所以m右边部分可以去掉了
- m不满足条件：范围变成[m + 1, r]，m不满足条件，比m小的就可以否定了(因为在求最小值之前 要先求 满足条件的最大值，如果这个m不满足条件的话说明比它小的值更不会满足条件了)
- 我之前想过一个可能：因为我们是直接取的一个数字去判断的，会不会我们最终找到的m值很接近res但不在最大值之列，那么求出的这个数不就有问题。其实不会出现这种可能：假设m = res + 1满足条件，m不会被返回，因为res比m小所以其实此时左边界和右边界还没有相等，m还会去和左边界的数进行比较直到找到res
话不多说，直接看题吧
1 //提供一个仅供参考的模板
2
3 int func(... ...){
4 int l = .., r = ..; // 根据题目要求得出二分范围
5
6 //判断函数,一般返回值为bool类型
7 auto check = [&](int m) {
8 ... ... // 根据题目要求写
9 };
10
11 //开始二分
12 while (l < r) {
13 int mid = l + (r - l) / 2;
14 if (check(m))
15 r = mid;
16 else
17 l = mid + 1;
18 }
19
20 return l;
21 }
1.6346. 打家劫舍 IV - 力扣（Leetcode）
1 class Solution {
2 public:
3 int minCapability(vector<int>& nums, int k) {
4 int l = nums[0], r = nums[0];
5 for (auto num : nums) {
6 l = min(l, num);
7 r = max(r, num);
8 }
9
10 int n = nums.size();
11 auto check = [&](int m) {
12 int cnt = 0;
13 for (int i = 0, j = - 2; i < n; ++ i) { //j是被偷窃的屋舍下标，当nums[0]被偷时，前一次被偷的是j = -2 家
14 if (nums[i] <= m && i - j > 1) {
15 j = i;
16 cnt ++;
17 }
18 }
19 return cnt >= k;
20 };
21
22 while (l < r) {
23 int mid = l + (r - l) / 2;
24 if (check(mid))
25 r = mid;
26 else
27 l = mid + 1;
28 }
29
30 return l;
31 }
32 };
2.2439. 最小化数组中的最大值 - 力扣（Leetcode）
1 class Solution {
2 public:
3 int minimizeArrayValue(vector<int>& nums) {
4 int n = nums.size();
5 int l = 0, r = nums[0];
6 for (auto num : nums) r = max(r, num);
7
8 auto check = [&](int m) {
9 vector<long long> copy(n);
10 for (int i = 0; i < n; ++ i) {
11 copy[i] = nums[i];
12 }
13
14 for (int i = n - 1; i > 0; i --) {
15 if (copy[i] > m) {
16 auto sub = copy[i] - m;
17 copy[i - 1] += sub;
18 }
19 }
20
21 return copy[0] <= m;
22 };
23
24 while (l < r) {
25 int mid = l + (r - l) / 2;
26 if (check(mid))
27 r = mid;
28 else
29 l = mid + 1;
30 }
31
32 return l;
33 }
34 };
改进版本（check部分），不用拷贝一份数组：
1 auto check = [&](int m) {
2 long sub = 0;//大于m的数字比m多出来的部分
3 for (int i = n - 1; i > 0; i --) {
4 if (nums[i] > m) {
5 sub += nums[i] - m;
6 } else if (nums[i] < m && sub > 0) {
7 sub -= m - nums[i];
8 if (sub < 0) {//说明多出来的部分在 被追加到前面数字上 的过程中消掉了，不会出现比m大的数字了，所以sub可以置0了。sub不可以为负数，因为题目是nums[i]可以将nums[i - 1] + 1，而不能使nums[i + 1] + 1
9 sub = 0;
10 }
11 }
12 }
13
14 if (sub <= 0)
15 return nums[0] <= m;
16 else
17 return nums[0] + sub <= m;
18 };
3.2513. 最小化两个数组中的最大值 - 力扣（Leetcode）
这个check卡了几次，有一个超时版本的，看了题解做出来了，贴一下题解
第9行处用long是因为可能会溢出，因为lcm函数是模板类，所以函数里面参数要强制转换一下
class Solution {
public:
int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
long long l = 0, r = 2 * (uniqueCnt1 + uniqueCnt2);
auto check = [&](int m) {
int cy1 = m / divisor1; // 可被 divisor1 整除的数：1倍的divisor1可以被整除，2倍的divisor1可以被整除，......，所以有m/division1个可以被整除的数
int cy2 = m / divisor2; // 可被 divisor2 整除的数
int cy = m / std::lcm(long(divisor1), long(divisor2)); //可被 divisor1 和divisor2 整除的数（这部分数字arr1和arr2都不可用）
int cnt1 = cy2 - cy; // arr1独享：cy2不能被arr2用，所以减去cy后就只能arr1用
int cnt2 = cy1 - cy; // arr2独享：与上同理
int cnt = m - cy1 - cy2 + cy; //共享，也可写成 cnt = m - cnt1 - cnt2 - cy(减去两者独享和两者都不能用的数字)
if (cnt1 < uniqueCnt1) {
int sub = uniqueCnt1 - cnt1;
if (cnt < sub) return false;
cnt -= sub;
}
if (cnt2 < uniqueCnt2) {
int sub = uniqueCnt2 - cnt2;
if (cnt < sub) return false;
}
return true;
};
while (l < r) {
int mid = l + (r - l) / 2;
if (check(mid))
r = mid;
else
l = mid + 1;
}
return l;
}
};
超时版本（主要是枚举超时）：
1 class Solution {
2 public:
3 int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
4 long long l = 0, r = 2 * (uniqueCnt1 + uniqueCnt2) ;
5
6 auto check = [&](int m) {
7 int cnt1 = 0, cnt2 = 0, cnt = 0;
8
9 for (int i = 1; i <= m; ++ i) {
10 int cy1 = i % divisor1, cy2 = i % divisor2;
11 if (cy1 != 0 && cy2 != 0) {
12 cnt ++; //共享的
13
14 } else if (cy1 != 0 && cy2 == 0) {
15 cnt1 ++;
16
17 } else if (cy1 == 0 && cy2 != 0) {
18 cnt2 ++;
19 }
20 }
21
22 if (cnt1 < uniqueCnt1) {
23 int sub = uniqueCnt1 - cnt1;
24 if (cnt < sub) return false;
25 cnt -= sub;
26 }
27
28 if (cnt2 < uniqueCnt2) {
29 int sub = uniqueCnt2 - cnt2;
30 if (cnt < sub) return false;
31 }
32
33 return true;
34 };
35
36 while (l < r) {
37 int mid = l + (r - l) / 2;
38 if (check(mid))
39 r = mid;
40 else
41 l = mid + 1;
42 }
43
44 return l;
45 }
46 };
标签：sub,nums,int,最大值,中求,mid,最小值,check From： https://www.cnblogs.com/balabalabubalabala/p/17094003.html