描述

通过不断缩小解可能存在的范围，从而求得问题的最优解的方法。

1. 求满足某个条件C(x)的最小x
2. 对于任意满足C(x)的x，如果所有的x’>=x也满足C(x’)的话，就可以使用二分法来求解最小的x。

适用情况

3. 假定一个解并判断是否可行
   leetcode 410 Split Array Largest Sum

C(x):得到m个数组和为x的子数组

#include <iostream>
#include<stdio.h>
#include<vector>
using namespace std;
vector<int>a;bool guess(long mid ,vector<int>& nums,int m){long sum=0;for(int i=0;i<nums.size();i++){if(sum+nums[i]>mid){m--;sum=nums[i];if(nums[i]>mid)return false;}elsesum+=nums[i];}return m>=1;}int splitArray(vector<int>& nums, int m){long R=1,L=0,ans=0;for(int i=0;i<nums.size();i++)R+=nums[i];while(L<R){long mid=(L+R)/2;if(guess(mid,nums,m)){ans=mid;R=mid;}else{L=mid+1;}}return (int)ans;}
int main()
{int n,k,temp;scanf("%d%d",&n,&k);for(int i=0;i<n;i++){scanf("%d",&temp);a.push_back(temp);}int ans=splitArray(a,k);printf("%d\n",ans);return 0;
}

2. 最大化最小值

C(x)：最近的距离为x

3. 最大化平均值

C(x)：可以得到均值不小于x的情况