【力扣刷題第四天-3】 機器人跳躍問題

文章目錄

• 前言
• 一、題目描述
• 二、解題思路
• 三、示例代碼
• 總結

前言

  本題主要考查 二分查找 算法。

提示：以下是本篇文章正文内容，程式設計語言為Java

一、題目描述

  機器人正在玩一個古老的基于 DOS 的遊戲。遊戲中有 N+1 座建築——從 0 到 N 編号，從左到右排列。編号為 0 的建築高度為 0 個機關，編号為 i 的建築的高度為 H(i) 個機關。

  起初， 機器人在編号為 0 的建築處。每一步，它跳到下一個（右邊）建築。假設機器人在第 k 個建築，且它現在的能量值是 E, 下一步它将跳到第個 k+1 建築。它将會得到或者失去正比于與 H(k+1) 與 E 之差的能量。如果 H(k+1) > E 那麼機器人就失去 H(k+1) - E 的能量值，否則它将得到 E - H(k+1) 的能量值。

  遊戲目标是到達第個 N 建築，在這個過程中，能量值不能為負數個機關。現在的問題是機器人最少以多少能量值開始遊戲，才可以保證成功完成遊戲？

示例 1：

輸入：
     5
     3 4 3 2 4
輸出：4
           

連結：機器人跳躍問題

二、解題思路

  我們假設最矮的建築物高度為

min

，最高的建築物高度為

max

， 我們可以很容易得出，機器人可以完成遊戲的初始能量範圍為

[min , max]

，是以我們就可以 二分能量

E

來得到機器人最少需要的初始能量。

  1） 當機器人可以完成遊戲時，那麼說明初始能量可能多了，是以更新右邊界

max = mid

；

  2） 當機器人不能完成遊戲時，那麼說明初始能量不夠，是以更新左邊界

min = mid +1

；

  此題還要注意能量的累積會導緻數值太大而越界，實際上當能量不小于最高的建築物高度時，機器人一定可以完成遊戲，是以就可以提前慶祝完成遊戲啦。

三、示例代碼

import java.util.*;

public class Solution{
    static int maxH;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int [] H=new int[n];
        int min=Integer.MAX_VALUE;
        int max=0;
        for(int i=0;i<n;i++){
            H[i]=sc.nextInt();
            min=Math.min(H[i],min);
            max=Math.max(H[i],max);
        }
        maxH=max;
        while(min<max){
           int mid=(min+max)>>1;
           
           //機器人可以完成遊戲，說明初始能量可能多了
           if(check(mid,H)){
               max=mid;
           }
           //機器人不能完成遊戲，說明初始能量不夠
           else{
               min=mid+1;
           }

        }
        System.out.println(max);
    }
    //判斷機器人是否可以完成遊戲
    public static boolean check(int E , int [] H){
        for(int i=0;i<H.length;i++){
            E=E+E-H[i];
            if(E<0){
                return false;
            }
            //能量已經可以确定完成遊戲了
            if(E>=maxH){
                return true;
            }
     }
    return true;
  }
}
           

總結

  本題可以很容易得到答案的一個範圍，是以我們就可以通過二分查找來确定最後的答案。

  同時，本題還有一個細節，能量的累積可能會導緻數值越界，是以要特判。