P2678:
题目描述
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。
输入格式
第一行包含三个整数 L,N,M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 L≥1 且N≥M≥0。
接下来 N 行，每行一个整数，第i 行的整数Di(0<Di<L)， 表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
输出格式
一个整数，即最短跳跃距离的最大值。
分析：
先贴一手洛谷Shownzhou大佬的一段话：
“那么什么时候适用二分答案呢？注意到题面：使得选手们在比赛过程中的最短跳跃距离尽可能长。如果题目规定了有
“最大值最小”或者
“
最小值最大”的东西，那么这个东西应该就满足二分答案的有界性（显然）和单调性（能看出来）。
那就好办了。我们二分跳跃距离，然后把这个跳跃距离“认为”是最短的跳跃距离，然后去以这个距离为标准移石头。使用一个
judge判断这个解是不是可行解。如果这个解是可行解，那么有可能会有比这更优的解，那么我们就去它的右边二分。为什么去右边？答案是，这个区间是
递增的 ，而我们求的是最短跳跃距离的
最大值，显然再右边的值肯定比左边大，那么我们就有可能找到比这更优的解，直到找不到，那么最后找到的解就有理由认为是区间内最优解。反过来，如果二分到的这个解是一个非法解，我们就不可能再去右边找了。因为性质，右边的解一定全都是非法解。那么我们就应该去左边找解。整个过程看起来很像递归，实际上，这个过程可以递归写， 也可以写成非递归形式，我个人比较喜欢使用非递归形式。
下一个问题，这个judge怎么实现呢？judge函数每个题有每个题的写法，但大体上的思想应该都是一样的——
想办法检测这个解是不是合法。拿这个题来说，我们去判断如果以这个距离为最短跳跃距离需要移走多少块石头，先不必考虑限制移走多少块，等全部拿完再把拿走的数量和限制进行比对，如果超出限制，那么这就是一个非法解，反之就是一个合法解，很好理解吧。”
这几句话对初学者我而言，可以说是圣经，建议反复阅读。
二分答案，需要我们在答案的可能区间内找出真正的答案，而寻找的方法就是二分，所以要求这个区间是单调的，是有界的。judge函数的判断是二分答案的核心，难一点的题可能就在这里下手。对于这一题，答案区间很明显就是【1，L】，有界而且递增。
judge函数就很关键。在这里，我们可以把区间【1，L】中的某一个数x作为结果，然后进行模拟，看看在最短跳跃距离的最大值为x的情况下，需要移走的岩石数m是多少。若m<M，行得通，但是我们仍然需要看看>x的数能否满足；m>M，说明x太大了，应在x的左边寻找答案。
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
ll n,m,l;
ll d[50005],f[50005];
bool judge(ll x)
{
ll cnt=0,now=0,i=1;
while(i<=n+1){
if(d[i]-d[now]<x) cnt++;//移走 i
//* 为什么还要考虑i==n+1 难道还能移走第n+1即终点的石头吗
else now=i;
i++;
}
if(cnt>m) return false;
else return true;
}
int main()
{
cin>>l>>n>>m;
for(ll i=1;i<=n;i++) cin>>d[i];
d[n+1]=l;
ll left=1,right=l;
while(left<=right){
ll mid=left+(right-left)/2;
if(judge(mid)) left=mid+1;
else right=mid-1;
}
cout<<right<<endl;
return 0;
}为什么还要考虑i==n+1 难道还能移走第n+1即终点的石头吗 ？
这个问题shownzhou大佬似乎也没有考虑到，为啥写i==n+1，而不是i==n，不是说不能移走终点即n+1号石头吗？其实，考虑i==n+1不再是为了移走i，而是要不要移走now，如果说d[n+1]-d[now]<x但是不能移动n+1，所以我们只能选择把我们现在踩着的位置的石头移除，cnt++。
这是讨论区的一位大佬贴的。%%%
P3853:
题目描述
现在政府决定在公路上增设一些路标，使得公路的“空旷指数”最小。他们请求你设计一个程序计算能达到的最小值是多少。请注意，公路的起点和终点保证已设有路标，公路的长度为整数，并且原有路标和新设路标都必须距起点整数个单位距离。
输入格式
第 1 行包括三个数 L,N,K，分别表示公路的长度，原有路标的数量，以及最多可增设的路标数量。
第 2 行包括递增排列的 N 个整数，分别表示原有的 N 个路标的位置。路标的位置用距起点的距离表示，且一定位于区间 [0,L] 内。
输出格式
输出 1 行，包含一个整数，表示增设路标后能达到的最小“空旷指数”值。
分析：
这个题其实和上一个题几乎一样，但是有好几个坑，我就每个坑都跳了一次。
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
ll L,n,k;
ll d[100002];
bool judge(ll x)
{
ll cnt=0,now=1;
for(int i=2;i<=n;i++){
if(d[i]-d[now]>x) {
cnt+=((d[i]-d[now])/x);
if((d[i]-d[now])%x==0) cnt--;
}
now=i;
}
if(cnt<=k) return true;
else return false;
}
int main()
{
cin>>L>>n>>k;
for(int i=1;i<=n;i++) cin>>d[i];
ll l=1,r=L,ans=0;
while(l<=r){
ll mid=l+(r-l)/2;
//二分答案 还是用ans写好
if(judge(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
cout<<ans<<endl;
return 0;
} 坑就是“思想被上一个题固化了”。这个是插，上一个是拔，当d[i]-d[now]>x时，我们需要插(d[i]-d[now])/x根柱子，注意如果(d[i]-d[now])%x==0，应该插(d[i]-d[now])/x-1根。
虽然说，这两个题难度都不是很高（当初一直WA的时候可不是这样说的），但是极大提高了我对二分答案的理解。
再次膜拜：Shownzhou大佬