NOIP2015 提高组 跳石头

发布时间:2024年01月24日

题目背景

NOIP2015 Day2T1

题目描述

一年一度的“跳石头”比赛又要开始了!这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。

为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 M 块岩石(不能移走起点和终点的岩石)。

输入格式

第一行包含三个整数 L, N, M,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。保证 L ≥ 1 且 N ≥ M ≥ 0。

接下来 N 行,每行一个整数,第 i 行的整数 Di (0 < Di < L),表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。

输出格式

一个整数,即最短跳跃距离的最大值。

样例 #1

样例输入 #1

25 5 2 
2
11
14
17 
21

样例输出 #1

4

提示

输入输出样例 1 说明

将与起点距离为 2 和 14 的两个岩石移走后,最短的跳跃距离为 4(从与起点距离 17 的岩石跳到距离 21 的岩石,或者从距离 21 的岩石跳到终点)。

数据规模与约定

对于 20% 的数据,0 ≤ M ≤ N ≤ 10。
对于 50% 的数据,0 ≤ M ≤ N ≤ 100。
对于 100% 的数据,0 ≤ M ≤ N ≤ 50000,1 ≤ L ≤ 10^9。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static StreamTokenizer sr = new StreamTokenizer(in);
    static int MAXN = 50000 + 10;
    static int[] arr = new int[MAXN];
    static int l, m, n;

    public static void main(String[] args) throws IOException {
        l = nextInt();
        n = nextInt();
        m = nextInt();
        for (int i = 1; i <= n; i++) {
            arr[i] = nextInt();
        }
        arr[n + 1] = l;
        int left = 0, right = l;
        while (left < right) {
            int mid = (right + left + 1) / 2;
            if (check(mid)) {
                // 尽可能大
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        out.println(left);
        out.flush();
    }

    private static boolean check(int mid) {
        int ans = 0;
        int cur = 0;
        for(int i = 1; i <= n + 1; i++) {
            if(arr[i] - cur < mid) {
                ans++;
            } else {
                cur = arr[i];
            }
        }
        if(ans <= m) {
            return true;
        }
        return false;
    }

    static int nextInt() throws IOException {
        sr.nextToken();
        return (int) sr.nval;
    }
}

以上是一道关于跳石头的题目,题目要求在给定的岩石序列中移除最多 M 个岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。我们可以使用二分查找的方法来解决这个问题。

具体的解题思路如下:

  1. 读入输入的 L、N、M 以及岩石序列。
  2. 将岩石序列按与起点距离从小到大排序,并在序列末尾添加一个距离为 L 的虚拟岩石。
  3. 使用二分查找的方法,在跳跃距离的范围内查找最大的合法跳跃距离。
  4. 在二分查找的过程中,使用 check 函数来判断当前跳跃距离是否合法。check 函数的具体实现如下:
    • 初始化 ans 和 cur 为 0。
    • 遍历岩石序列,如果当前岩石与上一个岩石的距离小于当前跳跃距离,则将 ans 加一。
    • 如果 ans 小于等于 M,则返回 true,否则返回 false。
  5. 输出最大的合法跳跃距离。
文章来源:https://blog.csdn.net/m0_73939789/article/details/135767739
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。