二分答案
二分答案
问题描述
二分答案是一种通过二分搜索可能解来找到最优解的技术。通常用于求解最大值最小化或最小值最大化的问题。
整数二分答案
算法思想
- 确定答案的取值范围[left, right)
- 二分枚举可能的答案
- 判断当前答案是否可行
- 根据判断结果缩小范围
代码实现
class Solution {
public:
bool check(vector<int>& nums, int maxSum, int m) {
int count = 1, sum = 0;
for (int num : nums) {
if (sum + num > maxSum) {
count++;
sum = num;
} else {
sum += num;
}
}
return count <= m;
}
int splitArray(vector<int>& nums, int m) {
int left = *max_element(nums.begin(), nums.end());
int right = accumulate(nums.begin(), nums.end(), 0) + 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (check(nums, mid, m)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
};
class Solution {
private boolean check(int[] nums, int maxSum, int m) {
int count = 1, sum = 0;
for (int num : nums) {
if (sum + num > maxSum) {
count++;
sum = num;
} else {
sum += num;
}
}
return count <= m;
}
public int splitArray(int[] nums, int m) {
int left = Arrays.stream(nums).max().getAsInt();
int right = Arrays.stream(nums).sum() + 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (check(nums, mid, m)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
class Solution:
def check(self, nums: List[int], max_sum: int, m: int) -> bool:
count, curr_sum = 1, 0
for num in nums:
if curr_sum + num > max_sum:
count += 1
curr_sum = num
else:
curr_sum += num
return count <= m
def splitArray(self, nums: List[int], m: int) -> int:
left = max(nums)
right = sum(nums) + 1
while left < right:
mid = left + (right - left) // 2
if self.check(nums, mid, m):
right = mid
else:
left = mid + 1
return left
实数二分答案
算法思想
- 确定答案的取值范围[left, right)
- 设定枚举次数（通常100次足够）
- 二分枚举可能的答案
- 根据判断结果缩小范围
代码实现
class Solution {
public:
bool check(vector<int>& stations, double dist) {
int count = 0;
for (int i = 1; i < stations.size(); i++) {
count += ceil((stations[i] - stations[i-1]) / dist) - 1;
}
return count <= k;
}
double minDistance(vector<int>& stations, int k) {
double left = 0;
double right = stations.back() - stations[0];
// 二分100次，相对误差约为2^(-100)
for (int i = 0; i < 100; i++) {
double mid = (left + right) / 2;
if (check(stations, mid)) {
right = mid;
} else {
left = mid;
}
}
return left;
}
};
class Solution {
private boolean check(int[] stations, double dist) {
int count = 0;
for (int i = 1; i < stations.length; i++) {
count += Math.ceil((stations[i] - stations[i-1]) / dist) - 1;
}
return count <= k;
}
public double minDistance(int[] stations, int k) {
double left = 0;
double right = stations[stations.length - 1] - stations[0];
// 二分100次，相对误差约为2^(-100)
for (int i = 0; i < 100; i++) {
double mid = (left + right) / 2;
if (check(stations, mid)) {
right = mid;
} else {
left = mid;
}
}
return left;
}
}
class Solution:
def check(self, stations: List[int], dist: float) -> bool:
count = 0
for i in range(1, len(stations)):
count += math.ceil((stations[i] - stations[i-1]) / dist) - 1
return count <= self.k
def minDistance(self, stations: List[int], k: int) -> float:
self.k = k
left = 0
right = stations[-1] - stations[0]
# 二分100次，相对误差约为2^(-100)
for _ in range(100):
mid = (left + right) / 2
if self.check(stations, mid):
right = mid
else:
left = mid
return left
时间复杂度分析
| 整数二分 | ||
| 实数二分 |
其中 是判定函数的时间复杂度，
是二分次数（通常取100）。
应用场景
- 最大值最小化
- 最小值最大化
- 资源分配问题
- 调度问题优化
- 距离问题求解
注意事项
- 答案范围的确定
- 判定函数的编写
- 精度要求的控制
- 整数与实数的区分
- 边界情况的处理
常见变形
- 最大值最小化
int minimizeMax(vector<int>& nums) {
sort(nums.begin(), nums.end());
int left = 0, right = nums.back() - nums.front() + 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (check(nums, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
class Solution {
public int minimizeMax(int[] nums) {
Arrays.sort(nums);
int left = 0, right = nums[nums.length-1] - nums[0] + 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (check(nums, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
class Solution:
def minimizeMax(self, nums: List[int]) -> int:
nums.sort()
left, right = 0, nums[-1] - nums[0] + 1
while left < right:
mid = left + (right - left) // 2
if self.check(nums, mid):
right = mid
else:
left = mid + 1
return left
- 最小值最大化
int maximizeMin(vector<int>& nums, int m) {
sort(nums.begin(), nums.end());
int left = 0, right = nums.back() - nums.front() + 1;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (check(nums, mid, m)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
class Solution {
public int maximizeMin(int[] nums, int m) {
Arrays.sort(nums);
int left = 0, right = nums[nums.length-1] - nums[0] + 1;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (check(nums, mid, m)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
}
class Solution:
def maximizeMin(self, nums: List[int], m: int) -> int:
nums.sort()
left, right = 0, nums[-1] - nums[0] + 1
while left < right:
mid = left + (right - left + 1) // 2
if self.check(nums, mid, m):
left = mid
else:
right = mid - 1
return left
经典例题
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
