侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

【二分查找】机器人跳跃问题

GabrielxD
2023-02-20 / 0 评论 / 0 点赞 / 341 阅读 / 784 字
温馨提示:
本文最后更新于 2023-02-20,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

730. 机器人跳跃问题 - AcWing题库


机器人正在玩一个古老的基于 DOS 的游戏。

游戏中有 N+1N+1 座建筑——从 00NN 编号,从左到右排列。

编号为 00 的建筑高度为 00 个单位,编号为 ii 的建筑高度为 H(i)H(i) 个单位。

起初,机器人在编号为 00 的建筑处。

每一步,它跳到下一个(右边)建筑。

假设机器人在第 kk 个建筑,且它现在的能量值是 EE ,下一步它将跳到第 k+1k+1 个建筑。

如果 H(k+1)>EH(k+1)>E ,那么机器人就失去 H(k+1)EH(k+1)-E 的能量值,否则它将得到 EH(k+1)E-H(k+1) 的能量值。

游戏目标是到达第 NN 个建筑,在这个过程中能量值不能为负数个单位。

现在的问题是机器人至少以多少能量值开始游戏,才可以保证成功完成游戏?

输入格式

第一行输入整数 NN

第二行是 NN 个空格分隔的整数, H(1),H(2),,H(N)H(1),H(2),…,H(N) 代表建筑物的高度。

输出格式

输出一个整数,表示所需的最少单位的初始能量值上取整后的结果。

数据范围

1N,H(i)1051 \le N,H(i) \le 10^5 ,

输入样例1:

5
3 4 3 2 4

输出样例1:

4

输入样例2:

3
4 4 4

输出样例2:

4

输入样例3:

3
1 6 4

输出样例3:

3

解题

方法一:二分查找

思路

二分初始能量的最小值,即二分左边界

二分 check 的过程中要注意的是:由于能量每次的变化量是 eh[i]e - h[i] ,所以当 eeh[i]h[i] 大一个数量级或以上时 ee 会很快地开始指数级增长(此时 ee 每次的增长量相当于它自身),此时 ee 将会很快地整型溢出甚至长整型溢出随后导致 check() 函数返回错误,所以当 eemax(h[0n])max(h[0\dots n]) 大时就可以认定此初始能量可行,直接返回 true 即可。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int n, mx;
    static int[] h;
    
    static boolean check(long e) {
        for (int i = 0; i < n; ++i) {
            e += e - h[i];
            if (e < 0) return false;
            if (e >= mx) return true;
        }
        return e >= 0;
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        h = new int[n];
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            h[i] = (int) in.nval;
            mx = Math.max(mx, h[i]);
        }
        int l = 0, r = mx;
        while (l < r) {
            int m = l + r >> 1;
            if (check(m)) r = m;
            else l = m + 1;
        }
        System.out.println(l);
    }
}
0

评论区