孙悟空吃蟠桃（E卷）

题目描述

孙悟空爱吃蟠桃，有一天趁着蟠桃园守卫不在来偷吃。已知蟠桃园有 N 棵蟠桃树，每棵树上都桃子，守卫将在 H 小时后回来。

孙悟空可以决定他吃蟠桃的速度 K （个/每小时），每个小时选一棵桃树，并从树上吃掉 K 个，如果K大于该树上所有桃子个数，则全部吃掉，并且这一小时剩余的时间里不再吃桃。

孙悟空喜欢慢慢吃，但又想在守卫回来前吃完桃子。

请返回孙悟空可以在 H 小时内吃掉所有桃子的最小速度 K （K 为整数）。如果以任何速度都吃不完所有桃子，则返回 0。

输入描述

第一行输入为 N 个数字， N 表示桃树的数量，这 N 个数字表示每棵桃树上蟠桃的数量。

第二行输入为一个数字，表示守卫离开的时间 H。

其中数字通过空格分割， N、 H 为正整数，每棵树上都有蟠桃，且 0 < N < 10000 , 0 < H < 10000。

输出描述

输出吃掉所有蟠桃的最小速度 K，无解或输入异常时输出 0。

示例1

输入:

2 3 4 5
4

输出：

5

示例2

输入：

2 3 4 5
3

输出：

0

示例3

输入：

30 11 23 4 20
6

输出：

23

解题思路

如果守卫离开的时间 H 小于桃树的数量，由于单位时间内只能在一棵树上吃，这种情况下无论如何是不能在守卫回来前将桃子吃完的。

其余情况，设置最大速度为一个较大值（超过单个桃树所拥有的最多桃子数量）, 这样方便辅助查找，利用 二分法进行折半查找。

源码 Java

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

public class Peach {

	Input input;

	@BeforeEach
	public void init() {
		// 测试用例
		input = new Input("30 11 23 4 20\n" +
			"6");
		input = new Input("2 3 4 5\n" +
			"4");
	}
	@Test
	public void peach() {
		String[] split = input.nextLine().split(" ");
		// split.length 数组长度为桃树数量
		int[] Ns = new int[split.length];
		for (int i = 0; i < split.length; i++) {
			// 转化为整型数据
			Ns[i] = Integer.parseInt(split[i]);
		}
		// 获取守卫离开时间
		int H = Integer.valueOf(input.nextLine());
		int speed = speed(Ns, H);
		System.out.println(speed);
	}

	/**
	 * 计算最小速度
	 * @param Ns  桃树信息
	 * @param H	守卫离开时间
	 * @return 孙悟空吃桃子的最小速度
	 */
	public int speed(int[] Ns, int H) {
		if (Ns.length > H) {
			return 0;
		}
		int right = 100000; // 设置右边界
		int left = 0;	// 设置左边界
		while (left < right) {// 退出条件
			int mid = (right + left) / 2;
			int time = 0; // 在速度 mid 下吃完所有桃子所需要的时间
			for (int i = 0; i < Ns.length; i++) {
				// 计算吃完一棵桃树所需要的时间
				time += (Ns[i] + mid - 1) / mid;
			}
			// 小于守卫离开的时间，说明在守卫回来前不能将桃子吃完，需要加快速度，缩小左边界
			if (time > H) { 
				left = mid + 1;
			} else {
				// 否则说明在守卫回来前，可以将桃子吃完，尝试使用更小的速度
				right = mid ;
			}
		}
		// 退出时 左右相等 即我们需要的速度
		return  left;
	}
}