河中跳房子游戏

问题描述

每年，奶牛们都举办一种特殊的跳房子游戏，在这个游戏中，大家小心翼翼地在河中的
岩石上跳。这个游戏在一条笔直的河中进行，以一块岩石表示开始，以另一块距离起点L
单位长度的岩石表示结束 (1 <= L <= 1,000,000,000)。在这两块岩石中间还有N
(0 <= N <= 50,000) 块岩石，每块的位置距离起点是 Di (0 < Di < L)个单位长度。

玩这个游戏的时候，每头牛从开始的那块岩石想办法要跳到表示结束的那块岩石上。中间
只能在从某块岩石跳跃到另一块岩石，反复的这样跳。当然，不够敏捷的牛永远跳不到终点，
最终只能落入河中。

农民 John 为他的牛感到自豪，每年都观看比赛。随着时间的推移，他对于那些胆小的
只能跳过很短距离的牛感到厌烦。为了那些牛，其他农民会把岩石的间距弄得很小。他
计划移除一些岩石，从而增加奶牛在跳跃时需要的最短距离。他不能移除开始和结束的两块
岩石。但是除此之外他可以移除 M (0 <= M <= N)块岩石。

FJ 希望知道他能够增加多少最短跳跃距离。求当他移除了M块岩石后，奶牛从开始跳到结束
的岩石，每次跳跃的最短距离至多可以增加到多少。

输入格式

行 1: 三个用空格分开的整数，分别是 L, N, 和 M

行 2..N+1: 每行一个整数，表示中间N块岩石的位置，没有两块岩石处于同一位置。

输出格式

行 1: 一个整数表示移除某M块岩石后，相邻岩石间距最小值的最大可能情况。

来一组小小的样例水得一匹 此处是四个贼贼的小字

样例输入

25 5 2 
2 
14 
11 
21 
17 

样例输出

4

分析：

　　分析题意：

　　每年，奶牛们都举办一种特殊的跳房子游戏，在这个游戏中，大家小心翼翼地在河中的
岩石上跳。这个游戏在一条笔直的河中进行，以一块岩石表示开始，以另一块距离起点L
单位长度的岩石表示结束 (1 <= L <= 1,000,000,000)。在这两块岩石中间还有N
(0 <= N <= 50,000) 块岩石，每块的位置距离起点是 Di (0 < Di < L)个单位长度。

玩这个游戏的时候，每头牛从开始的那块岩石想办法要跳到表示结束的那块岩石上。中间
只能在从某块岩石跳跃到另一块岩石，反复的这样跳。当然，不够敏捷的牛永远跳不到终点，
最终只能落入河中。

　　这一段话只是用来交代背景。及范围。

　　农民 John 为他的牛感到自豪，每年都观看比赛。随着时间的推移，他对于那些胆小的
只能跳过很短距离的牛感到厌烦。为了那些牛，其他农民会把岩石的间距弄得很小。他
计划移除一些岩石，从而增加奶牛在跳跃时需要的最短距离。他不能移除开始和结束的两块
岩石。但是除此之外他可以移除 M (0 <= M <= N)块岩石。

FJ 希望知道他能够增加多少最短跳跃距离。求当他移除了M块岩石后，奶牛从开始跳到结束
的岩石，每次跳跃的最短距离至多可以增加到多少。

　　进入正题了。通过每次跳跃的最短距离至多可以增加到多少。发现此题就是移除石头，让移除后让间距最小的两块石头之间的间距尽可能的大。

　　通俗一点，就是一句话：求最小的最大。

　　最小的最大，我们自然而然的想到了二分答案。

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------无耻的分割线

　　好的，我们来分析一下二分答案的过程：

　　1.一个最小值L，可以把它设为没有移除石头之前的最小间距，也可以直接设为1。（本人很懒，所以选择后者）。

　　2.一个最大值R，当然是从起点到终点的距离了（l（题目中的））。

　　3.分类讨论：

　　　　1.满足要求（移除m个石头可以使得最小值大于等于mid）：继续讨论有没有更大的可能。

　　　　2.不满足（移除m个石头不能使得最小值大于等于mid）：只能往小的一方去讨论。

　　二分代码如下：

　　

int L = 1;
int R = l;
while(L <= R){
    int mid = (L + R) / 2;
    if(isOk(mid)){
        L = mid + 1;
    } 
    else{
        R = mid - 1;
    }
} 

　　接下来我们来想想判断函数咋搞。

　　上代码吧，我们来看注释学习。

bool isOk(int mid){
    //last记录上一块停留的岩石距起点的距离 
    int Last = 0, cnt = 0;//cnt记录移走的石头数量
    for(int i = 1; i <= n; i++){
        if(d[i] - Last < mid){//需要移除了 
            cnt++;//移除 
            if(cnt > m){//已经不符合要求了（移除的石头数比m大） 
                return false;//返回false 
            }
        }
        else{
            Last = d[i];//不需要移除，last更新成为此时的这块岩石距起点的距离 
        }
    }
    return true;//如果不行已经在for中return了，所以符合 
}

　　好了，上整篇代码吧（无注释，随意粘）

　　

#include <bits/stdc++.h>

using namespace std;

int d[50000 + 5] = { };
int l, n, m;

bool isOk(int mid){
    int Last = 0, cnt = 0;
    for(int i = 1; i <= n; i++){
        if(d[i] - Last < mid){
            cnt++;
            if(cnt > m){
                return false;
            }
        }
        else{
            Last = d[i];
        }
    }
    return true;
}

int main(){
    scanf("%d %d %d", &l, &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d", &d[i]);
    }
    sort(d + 1, d + 1 + n);
    int L = 1;
    int R = l;
    while(L <= R){
        int mid = (L + R) / 2;
        if(isOk(mid)){
            L = mid + 1;
        } 
        else{
            R = mid - 1;
        }
    } 
    printf("%d", L - 1);
    
    return 0;
} 

　　谢谢大家观看，还是那一句：不喜勿喷qwq