【华为OD题库-009】食堂供餐-Java

题目

某公司员工食堂以盒饭方式供餐。为将员工取餐排队时间降低为0，食堂的供餐速度必须要足够快。现在需要根据以往员工取餐的统计信息，计算出一个刚好能达成排队时间为0的最低供餐速度。即，食堂在每个单位时间内必须至少做出多少份盒饭才能满足要求。
输入描述:
第1行为一个正整数N，表示食堂开餐时长。1<= N<= 1000。
第2行为一个正整数M，表示开餐前食堂已经准备好的盒饭份数。pi <= M<= 1000.
第3行为N个正整数，用空格分隔，依次表示开餐时间内按时间顺序每个单位时间进入食堂取餐的人数Pi。1 <=i<=N，0<= Pi<=100.
输出描述:
1个整数，能满足题目要求的最低供餐速度(每个单位时间需要做出多少份盒饭)
补充说明:
每人只取一份盒饭。
需要满足排队时间为0，必须保证取餐员工到达食堂时，食堂库存盒饭数星不少于本次来取餐的人数。第一个单位时间来取餐的员工只能取开餐前食堂准备好的盒饭。每个单位时间里制作的盒饭只能供应给后续单位时间来的取餐的员工，食堂在每个单位时间里制作的盒饭数量是相同的。
示例1
输入:
3
14
10 4 5
输出:
3
说明:
本样例中，总共有3批员工就餐，每批人数分别为10、4、5。开餐前食堂库存14份。
食堂每个单位时间至少要做出3份餐饭才能达成排队时间为0的目标。具体情况如下:
第一个单位时间来的10位员工直接从库存取餐。取餐后库存剩余4份盒饭，加上第一个单位时间做出的3份，库存有7份；第二个单位时间来的4位员工从库存的7份中取4份。取餐后库存剩余3份盒饭，加上第二个单位时间做出的3份，库存有6份；第三个单位时间来的员工从库存的6份中取5份，库存足够。
如果食堂在单位时间只能做出2份餐饭，则情况如下:第一个单位时间来的10位员工直接从库存取餐。取餐后库存剩余4份盒饭，加上第一个单位时间做出的2份，库存有6份；第二个单位时间来的4员工从库存的6份中取4分。取餐后库存剩余2份盒饭，加上第二个单位时间做出的2份，库存有4份；第三个单位时间来的员工需要取5份，但库存只有4份，库存不够。

思路

题目要求至少多少分盒饭，才能达到供餐要求，假设为x：
那么x最少为0；最大为max(arr)，arr为题目输入的第三行组成的数组。
这是一个典型的二分问题，我们可以写伪代码如下：

java">l=0 r=max(arr)
while(l<r):
	mid=l+r>>1;
	if(check(mid)):
		r=mid
	else:
		l=mid+1
return r

如果mid都能满足条件，那么供餐速度比mid大时，肯定也能满足，所以缩短右边界，继续在左边寻找看是否有更小的解。r=mid
如果mid不满足条件，那么比mid小的肯定也不满足条件，所以左边界右移：l=mid+1。
最后r和l一定相等，随便返回一个即可。
剩下的问题在于怎么实现check方法，根据题目要求，遍历arr，判断每次来取餐的人数是否大于当前剩余餐数即可。

题解

java">package hwod;

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

public class Canteen {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int time = sc.nextInt();
        int start = sc.nextInt();
        int[] nums = new int[time];
        for (int i = 0; i < time; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println(getMakeFoodSpeed(nums, start));
    }

    private static int getMakeFoodSpeed(int[] nums, int start) {
        int left = 0, right = Arrays.stream(nums).max().getAsInt();
        while (left < right) {
            int mid = left + right >> 1;
            if (checked(nums, start, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private static boolean checked(int[] nums, int start, int mid) {
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>start) return false;
            else start = start - nums[i] + mid;
        }
        return true;
    }
}

疑惑

题解的二分法和下面这种二分法，在本题上是等价的吗？如果不等价，那么什么样的用例数据能够显示出两者的差别？？

java">    private static int getMakeFoodSpeed(int[] nums, int start) {
        int left = 0, right = Arrays.stream(nums).max().getAsInt();
        while (left <= right) {
            int mid = left + right >> 1;
            if (checked(nums, start, mid)) {
                right = mid-1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }