算法日记2：洛谷p3853路标设置（二分答案）

一、题目：

二、解题思路：

2.1：首先，我们二分空旷指数

• 1、因为题目中要求我们求解最大值最小应该是属于第二类模型
• 2.也就是说，当check()函数为true时候，说明这个空旷指数是成立的，对应的路标数量 <k，此时，我们的路标还有没有使用过的，PS：路标增多，空旷指数一定是变小的
• 所以，我们此时应该让r=mid从而达成空旷指数减少
  
• 因此，代码如下：

	int l=0,r=L;
    while(l+1<r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;	//第二类模型
        else l=mid;
    }

2.2：check()函数解析

bool check(int mid) //表示当前可以达到这个'空旷指数'
{
    int cnt=0;  //放置的目标数量
    int i=0;    //用来枚举每一个路标，
    int now=0;  //表示当前跳到了某个路标
    
    while(i<n+1)
    {
        i++;
        while(a[i]-now>mid) //说明此时的两个路标不符合条件
        {
            cnt++;
            now+=mid;       // 新增一个路标
        }
        now=a[i];    // 更新当前的位置为下一个路标的位置
    }
    if(cnt<=k) return true;
    else return false;
}

	bool check(int mid) //表示当前可以达到这个'空旷指数'
	int cnt=0;  //放置的目标数量
    int i=0;    //用来枚举每一个路标，
    int now=0;  //表示当前跳到了某个距离

• 接下来我们来遍历每个路标while(i<n+1) i++
• 此时我们需要考虑，假如两个原定的路标在插入一个路标之后，仍然不满足条件，
  
• 1、如图所示，当我们在50--101之间插入了一个值之后，无论怎么插入，都是仍然不满足条件的
• 2、因此我们想，那么我们应该怎么插才会使得我们在一次插入后能达到最远的距离呢？
• 是不是应该是now+mid，这样我们就能使得这一次的插入性价比最高！！也就可以使得计算出这段距离的最少插入次数
• 随后更新我们目前的位置就好now=a[i]
• 最后比较cnt--k的值就好

三、完整代码如下：

#include<bits/stdc++.h>
using namespace std;

const int N=2e5;
int a[N];
int L,n,k;

bool check(int mid) //表示当前可以达到这个'空旷指数'
{
    int cnt=0;  //放置的目标数量
    int i=0;    //用来枚举每一个路标，
    int now=0;  //表示当前跳到了某个路标
    
    while(i<n+1)
    {
        i++;
        while(a[i]-now>mid) //说明此时的两个路标不符合条件
        {
            cnt++;
            now+=mid;       // 新增一个路标
        }
        now=a[i];    // 更新当前的位置为下一个路标的位置
    }
    if(cnt<=k) return true;
    else return false;
}




int main()
{
    cin>>L>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }

    int l=0,r=L;
    while(l+1<r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid;
    }
    
     cout<<r<<'\n';
    
	return 0;
}