数据结构与算法二分答案法
数据结构与算法：二分答案法
前言
二分答案法是很牛逼的一种算法，本质思想就是猜答案，然后看能不能对上条件。
一、内容
1.使用条件
只有当让你输出的 答案只有一个数 的时候，且 答案与给定条件之间存在单调性关系 时才能使用。
2.步骤
首先，要 先确定答案那个数的范围 。（范围大点无所谓）
之后，去找答案与给定条件的单调性关系。
然后使用二分搜索去范围上搜答案，每次使用一个函数判断答案能否满足题意。
二、题目
1.
class Solution {
public:
int minEatingSpeed(vector<int>& piles, int h) {
int l=1;
int r=0;
for(int i=0;i<piles.size();i++)
{
r=max(r,piles[i]);
}
int ans=0;
int m;
while(l<=r)
{
m=(l+r)/2;
if(f(m,piles)<=h)
{
ans=m;
r=m-1;
}
else
{
l=m+1;
}
}
return ans;
}
long long f(int speed,vector<int>&piles)
{
long long ans=0;
for(int i=0;i<piles.size();i++)
{
ans+=(piles[i]+speed-1)/speed;//向上取整
}
return ans;
}
};这个题很明显能想出，要求返回的速度与时间之间存在单调性关系，速度越大，时间越短。而且，这个速度存在一个范围，即1~每堆香蕉的数量最大值。因为速度最慢就是一次只吃一个，最快就是一次能把一堆都吃了，再快也没意义。
之后就是在答案范围上二分搜索，当此时的速度能满足时间要求，就记一下答案，然后去左侧看看速度更小时能否也满足时间；否则不记答案去右侧二分。
再就是判断函数，根据题意，让它按顺序吃就行，又因为一次最多只能吃一堆，所以这里相除时要向上取整，保证最后多吃一次把余数吃完。
2.
class Solution {
public:
typedef long long ll;
int splitArray(vector<int>& nums, int k) {
ll l=0;
ll r=0;
for(int i=0;i<nums.size();i++)
{
r+=nums[i];
}
ll ans=0;
ll m;
while(l<=r)
{
m=(l+r)/2;
if(f(m,nums)<=k)
{
ans=m;
r=m-1;
}
else
{
l=m+1;
}
}
return (int)ans;
}
ll f(int target,vector<int>&nums)
{
ll ans=0;
for(int i=0,sum=0;i<nums.size();i++)
{
if(nums[i]>target)
{
return INT_MAX;
}
if(sum+nums[i]>target)
{
ans++;
sum=nums[i];
}
else
{
sum+=nums[i];
}
}
return ans+1;
}
};这个题相比上一个题就不是那么好想了，首先分析单调性，可以发现，分割数和要求返回的最大值存在单调性关系，分割数越大，最大值越小。
之后是这个累加和最大值的范围，可以想到，最小就是0，最大就是不分割时整体的累加和。
之后就去二分搜索，当此时的累加和能分出的子数组数量比要求的小时，就记答案，然后去左侧更小的累加和看看能不能也满足要求的分割数；否则就不记答案去右侧二分。
判断函数就是若有一个数本身就比目标累加和大，直接返回无穷大表示不可能这么分；否则，若累加和比目标大，就让分割数+1即可。
3.
#include<bits/stdc++.h>
using namespace std;
bool f(int energy,int MAX,vector<int>&height)
{
for(int i=1;i<height.size();i++)
{
if(energy<=height[i])
{
energy-=height[i]-energy;
}
else
{
energy+=energy-height[i];
}
if(energy>=MAX)
{
return true;
}
if(energy<0)
{
return false;
}
}
return true;
}
int findEnergy(vector<int>&height)
{
int MAX=0;
for(int i=1;i<height.size();i++)
{
MAX=max(MAX,height[i]);
}
int ans=0;
int l=0;
int r=MAX;
int m;
while(l<=r)
{
m=(l+r)/2;
if(f(m,MAX,height))
{
ans=m;
r=m-1;
}
else
{
l=m+1;
}
}
return ans;
}
void solve()
{
int n;
cin>>n;
vector<int>height(n+1,0);
for(int i=1;i<=n;i++)
{
cin>>height[i];
}
cout<<findEnergy(height);
}
int main()
{
solve();
return 0;
}这个题的单调性能比上个题好想不少，分析可知，初始能量越大，越有可能到达终点。
之后是初始能量的范围，最小就是从0开始，最大就是高度的最大值，这样肯定能完成。
然后去二分，当此时能量能完成时，就记一下答案，然后去左侧看看更小的能量能否完成；否则不记答案去右侧二分。
注意判断函数里，为了剪枝和防止溢出，当此时能量比高度最大值大了就直接返回true，当能量小于0了就直接返回false。
4.
class Solution {
public:
int smallestDistancePair(vector<int>& nums, int k) {
//先排序
sort(nums.begin(),nums.end());
int l=0;
int r=nums[nums.size()-1]-nums[0];
int m;
int ans=0;
while(l<=r)
{
m=(l+r)/2;
if(f(m,nums)>=k)
{
ans=m;
r=m-1;
}
else
{
l=m+1;
}
}
return ans;
}
//差值<=limit的数对有几对
int f(int limit,vector<int>&nums)
{
int ans=0;
for(int l=0,r=0;l<nums.size();l++)
{
while(r+1<nums.size()&&nums[r+1]-nums[l]<=limit)
{
r++;
}
//l~r范围上的数差值均<=limit
ans+=r-l;
}
return ans;
}
};这个题和第二题的单调性说实话是真不好想，这个题是数对距离和数对数量存在单调性关系，距离越小，所对应的数对数量越多。
之后是范围，距离最小值就是0，两个数相等，最大就是数字最大值-最小值。
二分时，当此时的数对数量比要求的大时，就记答案，然后去左侧更小的地方看看能否也满足。
判断时，为了方便统计数对数量，所以先对数组排序。因为排序后子数组范围越大，距离越大，所以考虑使用滑动窗口。当距离小于等于limit时就让窗口增大，否则统计答案，即r-l的窗口大小，然后缩小窗口。
太难想了……
5.
class Solution {
public:
long long maxRunTime(int n, vector<int>& batteries) {
int MAX=0;
long long sum=0;
for(int i=0;i<batteries.size();i++)
{
MAX=max(MAX,batteries[i]);
sum+=batteries[i];
}
//若sum>=max*n，说明全是碎片电池
if(sum>=(long long)MAX*n)
{
return sum/n;
}
int ans=0;
int l=0;
int r=MAX;
int m;
while(l<=r)
{
m=(l+r)/2;
if(f(m,n,batteries))
{
ans=m;
l=m+1;
}
else
{
r=m-1;
}
}
return ans;
}
bool f(int time,int n,vector<int>&batteries)
{
for(long long i=0,sum=0;i<batteries.size();i++)
{
if(batteries[i]>time)
{
n--;
}
else
{
sum+=batteries[i];
}
if(sum>=(long long)time*n)
{
return true;
}
}
return false;
}
};这个比上个题能好想不少，单调性就是时间越长，越难达成。
其次是时间的范围。最小值肯定是0，最大值最初想到的肯定是所有电池的累加和。但如果进一步思考，用一点贪心的思想，当累加和>=所有电池的最大值*电脑数时，说明所有电池都是碎片电池，即不能单独完成要求时间内的供电，所以直接返回sum/n即可。否则，说明存在电池可以单独完成供电，那么此时的时间最大值就变成了电池的最大值。
二分时，当此时的时间能完成时，就记答案，然后去右侧更大的时间看看能否完成。
判断函数就是当有电池能独立完成供电，就让它一直待在这一个电脑，所以n-1；否则就计算电池累加和，若累加和>=时间*电脑数，说明能完成就返回true。
总结
二分答案法真的很妙！可以将复杂的问题转化成很简单的问题，而且由于二分搜索，所以时间复杂度也很优秀。当遇到答案为一个单一的数时就可以分析题目单调性，考虑使用二分答案。所以加上之前的滑动窗口双指针，题目的单调性真的很重要！