205008 - 跳石头

题解bytianmeng

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define INF 0x7ffffff
#define maxn 2000000
using namespace std;
int n,a[maxn],m,ll,rr,l,s,num,mid,ans;
int half(int x)//x是目前的理想距离 
{
    s=0,num=0;//num是计数器，记录移走的石头数目，s计数器，是指目前的石头离起点的距离（难理解？看底下一层循环） 
    for(int i=1;i<=n+1;i++)
{
         //枚举第1到终点的n+1块石头 if(a[i]-s<x)//如果第i块石头的距离减去s，什么意思？这两块石头之间的距离！ 若两块之间的距离<期望的距离
num++;//移走的数目+1，因为你要的是移走0~m块石头，使他们之间的距离都大于等于m
else s=a[i];//若距离大于期望距离了，s更新到i的距离
//枚举完了，统计完了移走的数目
}
if(num>m) return 0;
//如果移走石块>m才能到期望距离，就是不满足条件
    return 1;//否则就是满足条件 
}
int main()
{
    scanf("%d%d%d",&l,&n,&m);
    for(int i=1;i<=n;i++)
     scanf("%d",&a[i]);
    a[n+1]=l;//n是终点前的最后一块石头，所以a[n+1]=l，记录终点的值 
    ll=0,rr=l;//定义一个二分边界 
    while(ll<=rr)//当左右边界重合的时候就是答案，退出循环 
     {
         mid=(ll+rr)/2;//取两边界的中间值，枚举一个最大距离 
         if(half(mid))//当该距离满足条件的时候 
{
              //去寻找右半部分，看看还有没有符合条件的更大的值
              ll=mid+1;//ll上mid右边，找右半部分 
              ans=mid;//记录答案（更新中） 
          }
        else rr=mid-1;//若这个值不满足，就找左部分 
     }
    printf("%d",ans);//输出答案（循环时已经更新了） 
    return 0;
}