一、题目描述
某公司员工食堂以盒饭的方式供餐。
为将员工取餐排队时间降为0，食堂的供餐速度必须要足够快。
现在需要根据以往员工取餐的统计信息，计算出一个刚好能达到排队时间为0的最低供餐速度。
即，食堂在每个单位时间内必须至少做出多少份盒饭才能满足要求。
二、输入描述
第一行输入一个正整数N，表示食堂开餐时长。
第二行为一个正整数M，表示开餐前食堂已经准备好的盒饭数量；
第三行为N个正整数，用空格分割，依次表示开餐时间内按时间顺序每个单位时间进入食堂取餐的人数。
三、输出描述
一个整数，能满足题目要求的最低供餐速度。（每个单位时间需要做出多少份盒饭）。
四、补充说明
每人只能取一份盒饭。
需要满足排队时间为0，必须保证取餐员工到达食堂时，食堂库存盒饭数量不少于本次来取餐的人数。
第一个单位时间来取餐的员工只能取开餐前食堂准备好的盒饭。
每个单位时间里制作的盒饭只能供给后续单位时间来的取餐员工。食堂在每个单位时间里制作的盒饭数量是相同的。
四、解题思路
- 采用二分法；
- left为最小出餐速度，right为最大出餐速度 = 总人数 - 已经准备好的盒饭数量；
- 判断是否还剩余盒饭；
- 如果盒饭不够了，返回false；
- 如果盒饭足够，则剩余盒饭数量 = 目前盒饭数量 - 每个时间段的取餐人数，再加上当前时间段生产的盒饭数量；
五、Java算法源码
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 食堂开餐时长
int N = in.nextInt();
// 开餐前食堂已经准备好的盒饭数量
int M = in.nextInt();
// 每个单位时间进入食堂取餐的人数
int[] P = new int[N];
// 总人数
int count = 0;
for (int i = 0; i < N; i++) {
P[i] = in.nextInt();
count += P[i];
}
// 最小出餐速度
int left = 0;
// 最大出餐速度 = 总人数 - 已经准备好的盒饭数量
int right = count - M;
while (left < right) {
//二分法
int mid = (left + right) / 2;
// 是否还有剩余盒饭
if (check(mid, M, N, P)) {
right = mid;
} else {
left = mid + 1;
}
}
// 最小出餐速度
System.out.println(left);
}
/**
* 是否还有剩余盒饭
* @param speed
* @param M 已经准备好的盒饭数量
* @param N 食堂开餐时长
* @param P 每个单位时间进入食堂取餐的人数
* @return
*/
public static boolean check(int speed, int M, int N, int[] P) {
boolean result = true;
for (int i = 0; i < N; i++) {
// 剩余盒饭数量 = 目前盒饭数量 - 每个时间段的取餐人数
M -= P[i];
// 如果盒饭不够了，返回false
if (M < 0) {
result = false;
break;
}
M += speed;
}
return result;
}
六、效果展示
1、输入
3
20
15 12 8
2、输出
8
3、说明
开产前食堂库存20份。
第一个单位时间段，有15人来取餐，取餐后剩余5份，加上第一个单位时间做出来的8份，还剩13份；
第二个单位时间段，有12人来取餐，取餐后剩余1份，加上第二个单位时间做出来的8分，还剩9份；
第三个单位时间段，有8人来取餐，盒饭数量还剩9个，足够了。
🏆下一题：华为OD机试真题 Java 实现【最多提取子串数目】【2023Q1 100分】
🏆本文收录于，华为OD机试（JAVA）（2022&2023）
本专栏包含了最新最全的2023年华为OD机试真题，有详细的分析和Java解答。已帮助1000+同学顺利通过OD机考。专栏会持续更新，每天在线答疑。