11575: 【原1575】river

题目描述

author: ZH 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1575

Description

一只青蛙想要过河向长者学习生存技巧。在它面前有一条宽为L的河流，河上有N片荷叶，荷叶距离河岸的距离为Di，这些荷叶的连线恰好与河岸垂直，青蛙想要踩着这些荷叶从河的一端(起点)到河的另一端(终点)。严格的你在河边看到了这番场景，觉得这对于熟练的青蛙来说太简单了。你决定摘走若干片荷叶(有股神秘的力量能让你隔空取物)，使得相邻荷叶之间的间距的最小值尽可能大，从而可以加大青蛙过河的难度。但是由于你背包容量限制，最多能摘M片荷叶。请问在此条件下荷叶最短间距的最大值是多少？

注：青蛙必须踩到所有仍在河上的荷叶才能过河。

Input Format

第一行有三个整数\(L,N,M\) ，分别代表起点与终点的距离，中间的荷叶数以及最多能摘走的荷叶数，保证L>=1且N>=M>=0。

接下来\(N\) 行，每行一个整数Di(0<Di<L)，代码荷叶与起点的距离。这些距离已经按升序排序且没有两个数相同。

Output Format

共一行，一个整数，表示摘掉若干荷叶后最短间距的最大值。

Sample Input

Sample Output

Sample Explanation

摘走距离起点2和14的两个荷叶，剩下11 17 21，则最小距离为21-17=25-21=4。

Limits

对于\(20\%\)的数据，1 <= n, m <= 10,。
对于\(50\%\)的数据，1 <= n, m <= 100。
对于\(100\%\)的数据，1 <= n, m <= 50000, L <= 10^9。

yyong119's solution

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_N = 50010;

int main() {

    ios::sync_with_stdio(false);
    int l, n, m;
    cin >> l >> n >> m;
    int a[MAX_N]; a[0] = 0; a[n + 1] = l;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    int L = 1, R = l, mid, remove;
    while (L < R) {
        int b[MAX_N];
        memcpy(b, a, sizeof(a));
        mid = (L + R) >> 1; remove = 0;
        for (int i = 1; i <= n + 1; ++i)
            if (b[i] - b[i - 1] < mid) {
                b[i] = b[i - 1];
                if (++remove > m) break;
            }
        if (remove <= m) L = mid + 1; else R = mid - 1;
    }
    int k;
    for (k = mid + 1; k >= mid - 1; --k) {
        int remove = 0;
        int b[MAX_N];
        memcpy(b, a, sizeof(a));
        for (int i = 1; i <= n + 1; ++i)
            if (b[i] - b[i - 1] < k) {
                b[i] = b[i - 1];
                if (++remove > m) break;
            }
        if (remove <= m) break;
    }
    cout << k << endl;
    return 0;
}