前言

秒懂百科，C++如此简单系列终于更新啦！

Everyday English

Yesterday is history, tomorrow is a mystery, but today is a gift.

昨天是历史,明天是个谜,今天是礼物。把握好当下。

二分查找和二分答案

一看到标题是二分是不是就感觉以前学过，的确在第十一天时，我们就已经学过了。网址：秒懂百科，C++如此简单丨第十一天：二分查找-CSDN博客

但是，你仔细一读标题会发现，我们今天学的是二分答案。

那他俩有啥区别呢，顾名思义。二分查找是去找一个数，而二分答案是去二分某一题的答案，直至满足题目所问。

但是不管怎样，都有可能会用到以下程序：

<code>while(l<=r)

{

mid=(l+r)/2;

if()

{

l=mid+1;

}

else

{

r=mid-1;

}

}

为什么说有可能呢？我们来看一道题目。

洛谷 P3881 栓奶牛

网址：[信息与未来 2015] 拴奶牛 - 洛谷

理解问题

这题目一出来，你是不是看得云里雾里？有两个地方很绕，我们来一起看一看。

1.Pi = Pi-1 + ((Pi-1 x 2357 + 137) mod 10) + 1

这个其实是k个木桩位置的生成方式。你不要管数字有多么大，你只要按照说的做就行了。

因为已经给出P1了，那么从P2开始，带入这个式子，就可以依次算出来所有木桩的位置了。

2.最近距离的最大值

不要被最近和最大绕进去了。我来问问你，如果相隔距离为100可以实现，那么距离为1是不是也能实现？也就是说小的都能实现，但我们要求出其中最大的。

思路点拨

我们可以写一个二分答案的程序，如果这个答案能满足条件，我们就先记录下来，但是我们想要答案尽可能的大，我们得让左指针移动到mid+1。

否则，让右指针移动到mid-1，说明我们答案太大了，满足不了条件。

那我们怎么写检查答案是否满足这个条件呢？

其实很简单，你这要用mid照着题目意思模拟即可。

当遇到一个木桩，用sum+当前木桩与前一个木桩的差值。一但sum>=mid，就让计数器+1，sum=0。

最后看一眼计数器是否能栓题目所给的数量（大于等于都可以）

AC代码

<code>#include<bits/stdc++.h>

using namespace std;

long long n,k,k1,a[10000000];

bool check(long long mid)

{

long long kk=1;//kk为计数器，注意第一头奶牛已经默认栓在第一个木桩

long long sum=0;

for(long long i=1;i<=k;i++)

{

sum+=a[i+1]-a[i];//加上差值

if(sum>=mid)//如果>=mid的值，这里mid是两头牛之间的距离

{

kk++;

sum=0;

}

}

if(kk>=n) return 1;

else return 0;

}

int main()

{

cin>>n>>k>>k1;

a[1]=k1;

for(long long i=2;i<=k;i++)

{

a[i]=a[i-1]+((a[i-1]*2357+137)%10)+1;//照着式子带入

}

long long l=1,r=a[k],mi,t;//l最小是1，r最大是最后一个木桩的坐标

while(l<=r)

{

mi=(l+r)/2;//二分答案

if(check(mi))//如果满足题目

{

t=mi;//先记录一下答案

l=mi+1;//看看还有没有更大的

}

else

{

r=mi-1;//数字太大了，满足不了

}

}

cout<<t<<endl;

return 0;

}

扩展补充 

既然有最小值中的最大值，那么有没有最大值中的最小值呢？答案是肯定的！

代码整体思路是一样的，但要注意如果满足条件应该找一找有没有更小的答案。

所以说满足条件时，r=mid-1。否则l=mid+1，数字太小了，满足不了条件。

总结

今天我们一起学习了二分答案，给你详细讲了一道题目。不知道你有没有收获呢？

如果觉得本篇文章还不错的话，希望你能送上手中点赞、收藏和评论，这对我来说很重要。

我是爱编程的小芒果，我们下篇再见！Bye~