A49.跳石头 题解

代码有详细注释

#include <bits/stdc++.h>
using namespace std;
long long n,m,x;//n：起点到终点的距离 	m：起点与终点之间石头的个数  	x：至多能够移动的次数 
long long a[10000100];//每块石头距离起点的最大值 
long long l,r;//二分的答案的上界（r），下界（l） 
long long dif[10000100] = {0};//差分数组 


bool check(int mid)
{
    long long temp = 0;//统计需要移走多少次石头 
    long long tdif[m + 1] = {0};
	/*临时数组 （复制差分数组）， 在统计需要移走多少次石头的时候会修改数组内元素 ， 
	复制差分数组是为了不破坏差分数组 */ 
    //复制 
    for(int i = 0;i <= m;i++)
    {
        tdif[i] = dif[i];
    }
    //统计需要移走多少次石头
    for(int i = 0;i <= m;i++)
    {
        if(tdif[i] < mid)//如果  当前最短跳跃距离的长度  比  目标长度 要短 
        {
            temp++;//需要移走一块石头 
            tdif[i + 1] += tdif[i];//移走石头之后要与下一块石头的差分合并 
        }
    }
    
    if(temp <= x) 
    {
        return true;
    }
    else
    {
        return false;
    }
}


int main()
{
    scanf("%lld%lld%lld",&n,&m,&x);
    for(int i = 0;i < m;i++)
    {
        scanf("%lld",&a[i]);
        r = max(r,a[i]);//上界是数组中石头距离a数组的中的最大值 
        //计算差分  
        if(!i)//其实是 i == 0 的变形 ，如果 i == 0直接用差分数组会越界，所以加个判断 
        {
            dif[i] = a[i];
        }
        else
        {
            dif[i] = a[i] - a[i - 1];
        }
    }
    dif[m] = n - a[m - 1];// 终点石头的差分也要算上，终点石头的差分是 总长高度（n） -  a数组的最后一个元素 
    
    
    //没有石头，也就没有机会移动，也就是说答案就是总长度 ，即 n 
    if(m == 0)
    {
        printf("%lld",n);
        return 0;
    }
    
    
    l = 1;//距离不可能为 0，所以是下界是 1 
    long long ans = 0;//答案 
    
    
    while(l <= r)
    {
        long long mid = l + (r - l) / 2;//计算中间值 
        
        if(check(mid))
        {
        	//如果移动石头的次数比最多可以移动的次数要少 
        	
        	//更新答案 
            ans = mid;
            //目标数值越大，需要移动的次数就越多，又因为现在要移动的次数比 m 小，要往次数更多的值找 
            l = mid + 1;
        }
        else
        {
        	//需要移动的次数太多了，往小的找 
            r = mid - 1;
        }
    }
    
    printf("%lld",ans);
    return 0;
}