蓝桥杯2022年第十三届省赛真题-青蛙过河(二分查找+前缀和)-526互联

题目描述

小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。

河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降 1，当石头的高度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到 0 是允许的）。

小青蛙一共需要去学校上 x 天课，所以它需要往返 2x 次。当小青蛙具有一个跳跃能力 y 时，它能跳不超过 y 的距离。

请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课。

输入格式

输入的第一行包含两个整数 n, x，分别表示河的宽度和小青蛙需要去学校的天数。请注意 2x 才是实际过河的次数。

第二行包含 n − 1 个非负整数 H1, H2, · · · , Hn-1，其中 Hi > 0 表示在河中与小青蛙的家相距 i 的地方有一块高度为 Hi 的石头，Hi = 0 表示这个位置没有石头。

输出格式

输出一行，包含一个整数，表示小青蛙需要的最低跳跃能力。

样例输入

5 1
1 0 1 0

样例输出

提示

由于只有两块高度为 1 的石头，所以往返只能各用一块。第 1 块石头和对岸的距离为 4，如果小青蛙的跳跃能力为 3 则无法满足要求。所以小青蛙最少需要 4 的跳跃能力。

对于 30% 的评测用例，n ≤ 100；

对于 60% 的评测用例，n ≤ 1000；

对于所有评测用例，1 ≤ n ≤ 105 , 1 ≤ x ≤ 109 , 1 ≤ Hi ≤ 104。

解答：

1，对于跳跃能力，如果可以跳n格，那么，如果n格内的石头足够你跳2x（题目要求的x天并往返）次，说明跳跃能力n满足条件，题目要求是找到最低的

n并且满足条件，所以，我们可以使用二分查找，如果河宽度的m（mid）满足要求则缩小范围尝试更低的n，反之扩大范围尝试更高的n

private static int binarySearchJump() {
        int l = 0, r = n;
        int ans = r;
        while (l <= r) {
            int m = (l + r) >>> 1;
            if (isJump(m)) {
                ans = Math.min(ans, m);
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return ans;
    }

isJump方法是判断当前查找的m是否满足条件

2，使用前骤和防止重复计算，因为isJump判断需要判断n格内是否能让你条2x次

　　　　x = sc.nextInt();
        x *= 2;
        H = new int[n+1];
        pre = new int[n];
        for (int i = 1; i < n; i++) {
            H[i] = sc.nextInt();
            pre[i] = pre[i-1] + H[i];
        }

H记录每个石头的高度（跳一次减一，也就是每个石头的跳跃次数）

使用pre数组当作前奏和

3，实现isJump方法，为了保证n的跳跃能力能够满足条件，我们需要判断每一个长度为n的区间是否足够跳跃n此（代码中的y就是描述中的n）

private static boolean isJump(int y) {
        for (int i = 0; i < n - y; i++) {
            if (pre[i + y] - pre[i] < x) {
                return false;
            }
        }
        return true;
    }

全代码如下：

import java.util.Scanner;

public class H {
    static int n, x;
    static int[] H;
    static int[] pre;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        x = sc.nextInt();
        x *= 2;
        H = new int[n+1];
        pre = new int[n];
        for (int i = 1; i < n; i++) {
            H[i] = sc.nextInt();
            pre[i] = pre[i-1] + H[i];
        }
        System.out.println(binarySearchJump());
    }

    private static int binarySearchJump() {
        int l = 0, r = n;
        int ans = r;
        while (l <= r) {
            int m = (l + r) >>> 1;
            if (isJump(m)) {
                ans = Math.min(ans, m);
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return ans;
    }

    private static boolean isJump(int y) {
        for (int i = 0; i < n - y; i++) {
            if (pre[i + y] - pre[i] < x) {
                return false;
            }
        }
        return true;
    }
}