【华为OD题库-104】猴子吃桃-java

题目

题目描述:
孙悟空喜欢吃蟠桃，一天他乘守卫蟠桃园的天兵天将离开了而偷偷的来到王母娘娘的蟠桃园偷吃蟠桃。
已知蟠桃园有棵蟠桃树，第i棵蟠桃树上有Ni个蟠桃，天兵天将将在H(不小于蟠桃树棵数)小时后回来。
孙悟空可以决定他吃蟠桃的速度K(单位:个小时)，每个小时他会选择一颗蟠桃树，从中吃掉K个蟠桃，如果这棵树上的蟠桃数小于K，他将吃掉这棵树上所有蟠桃，然后这一小时内不再吃其余蟠桃树上的蟠桃。
孙悟空喜欢慢慢吃，但仍想在天兵天将回来前将所有蟠桃吃完。
求孙悟空可以在H小时内吃掉所有蟠桃的最小速度K(K为整数)。
输入描述:
从标准输入中读取一行数字，前面数字表示每棵数上蟠桃个数，最后的数字表示天兵天将将离开的时间。
输出描述:
吃掉所有蟠桃的最小速度K(K为整数)或输入异常时输出-1。
示例1:
输入
3 11 6 7 8
输出
4
说明:
天兵天将8个小时后回来，孙悟空吃掉所有蟠桃的最小速度4。
第1小时全部吃完第—棵树，吃3个，
第2小时吃4个，第二棵树剩7个，
第3小时吃4个，第二棵树剩3个，
第4小时吃3个，第二棵树吃完，
第5小时吃4个，第三棵树剩2个，
第6小时吃2个，第三棵树吃完，
第7小时吃4个，第4棵树剩3个，
第8小时吃3个，第4棵树吃完。

思路

同leetcode 875. 爱吃香蕉的珂珂

区别在于需要判定-1的情况（输入异常），如果输入的数组长度为1或者，天兵天将回来的时间过早，直接输出-1

题解

package hwod;

import java.util.Arrays;
import java.util.Scanner;

public class MonkeyPeach {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        System.out.println(monkeyPeach(nums));
    }

    private static int monkeyPeach(int[] nums) {
        int target = nums[nums.length - 1];

        int n = nums.length - 1;
        int[] newNums = new int[n];
        if (n <= 0 || target < n) return -1;

        int left = 1, right = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] > right) right = nums[i];
            newNums[i] = nums[i];
        }

        while (left < right) {
            int mid = left + ((right - left) >> 1);
            int time = getTime(newNums, mid);
            if (time > target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private static int getTime(int[] newNums, int mid) {
        int res = 0;
        for (int i = 0; i < newNums.length; i++) {
            res += (newNums[i] + mid - 1) / mid;
        }
        return res;
    }
}

推荐

如果你对本系列的其他题目感兴趣，可以参考华为OD机试真题及题解（JAVA），查看当前专栏更新的所有题目。