蓝桥杯刷题——day3-题目二

时间：2024-12-19 07:03:47

题干

小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降1，当石头的高度下降到0时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到0 是允许的)。小青蛙一共需要去学校上x 天课，所以它需要往返2x 次。当小青蛙具有一个跳跃能力y 时，它能跳不超过y 的距离。请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课。
输入格式：
输入的第一行包含两个整数n,x, 分别表示河的宽度和小青蛙需要去学校的天数。请注意2x 才是实际过河的次数。第二行包含n−1 个非负整数 表示在河中与 小青蛙的家相距i的地方有一块高度为h的石头，h=0则表示没有石头。
输出格式：
输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。
示例一：

输入：
5 1
1 0 1 0
输出：
4

题目链接：青蛙过河

题目解析

这是一个典型的二分查找加模拟的问题。小青蛙需要在有限的石头高度和跳跃能力的限制下完成往返 2x 次。以下是解决问题的详细思路：

  1. 最小跳跃能力y 的范围是从 1 到n，我们可以用二分查找找到最小的y，使得小青蛙能够完成2x 次过河。
  2. 给定一个跳跃能力y，模拟小青蛙的跳跃过程，检查是否能完成2x 次过河。然后每次跳跃时，石头高度减 1，不能跳到高度为 0 的石头上。
  3. 判断是否满足条件的方法用模拟实现。如果当前 y 能够完成2x 次过河，则尝试更小的 y；否则增加 y。

下面是完整代码：

代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入河宽度和需要去学校的天数
        int n = scanner.nextInt();
        int x = scanner.nextInt();

        // 输入石头高度
        int[] stones = new int[n];
        for (int i = 1; i < n; i++) {
            stones[i] = scanner.nextInt();
        }

        // 二分查找最低跳跃能力
        int left = 1, right = n, result = n;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (canCross(stones.clone(), mid, 2 * x)) {
                result = mid; // 当前跳跃能力可行，尝试更小值
                right = mid - 1;
            } else {
                left = mid + 1; // 当前跳跃能力不足，增加跳跃能力
            }
        }

        // 输出结果
        System.out.println(result);
    }

    // 判断是否能完成指定次数的过河
    public static boolean canCross(int[] stones, int jump, int trips) {
        int n = stones.length;

        for (int t = 0; t < trips; t++) {
            int position = 0; // 从起点出发
            while (position < n - 1) {
                int next = position;
                // 找到能跳到的最远位置
                for (int j = position + 1; j < n && j <= position + jump; j++) {
                    if (stones[j] > 0) {
                        next = j;
                    }
                }

                if (next == position) {
                    // 无法前进，跳跃失败
                    return false;
                }

                // 跳到 next，石头高度减 1
                stones[next]--;
                position = next;
            }
        }

        return true; // 成功完成所有 trips
    }
}

main函数其实很好理解就是一个二分查找的问题，我们看canCross函数，在这个函数模拟小青蛙从起点出发，经过石头跳到对岸的过程。外层循环 for (int t = 0; t < trips; t++)循环模拟小青蛙过河的过程。因为小青蛙需要往返2x 次，所以我们要模拟trips 次跳跃，while (position < n - 1)循环则检查小青蛙是否跳到了对岸，for (int j = position + 1; j < n && j <= position + jump; j++) 循环则是找小青蛙能跳到的最远距离，当我们发现next == position时，就表明小青蛙一动不动，也就是跳跃失败，否则石头的高度减去1，并且更新position。这段代码我并没有完全通过编译器，其出现的问题我也不太清楚，如果发现问题，欢迎私信和评论，感谢各位的点赞。

相关文章