华为OD机考算法题：食堂供餐

目录

题目部分

解析与思路

代码实现

---

题目部分

---

解析与思路

题目解读：

此题中，第1行是就餐员工的总批数，设为 count；第2行是初始库存数，设为 stockQty；第3行是每批次的份数，假设每批次的数字放到数组 dinners 中，那么dinners的长度为count，且dinners[i] 即为第 ( i + 1 ) 个批次所需的份数（备注：批次起始值为1，放到数组的第 0 个元素）。

假设题目中最低的供餐速度为 x（x为正整数），那么 对于所有的 i ( 0 <= i <= count)，x 必须满足 （ stockQty + x * i） >=  ∑idx=0idinners[idx]" role="presentation" style="position: relative;">∑iidx=0dinners[idx]$\sum _{idx=0}^{i}dinners[idx]$。其中， ∑idx=0idinners[idx]" role="presentation" style="position: relative;">∑iidx=0dinners[idx]$\sum _{idx=0}^{i}dinners[idx]$ 代表着dinners数组的前 i 个元素之和，即 ∑idx=0idinners[idx]" role="presentation" style="position: relative;">∑iidx=0dinners[idx]$\sum _{idx=0}^{i}dinners[idx]$ = dinners[0] + dinners[1] + … + dinners[i]。

分析思路：

虽然此题的难度设置为“难”，实际解题思路比较简单。

设置 x 的初始值为0。

根据不等式 （ stockQty + x * i） >=  ∑idx=0idinners[idx]" role="presentation" style="position: relative;">∑iidx=0dinners[idx]$\sum _{idx=0}^{i}dinners[idx]$，对于 i， 从 0 到 ( count -1 ) ，判断当前的 x 值是否保证不等式成立：

• 如果不等式成立，则不进行任何操作；
• 如果不等式不成立，即 x 值过小，重新计算 x 的值。计算后，x 的新值必定比老值大。
  我们知道，当 从 0 到 ( i - 1 )， x 的老值都能保证不等式成立，当 x 值变大，不等式的左边比以前更大。这意味着当 x 取新值（更大的值）时，这个不等式在 0 到 ( i - 1 )  一定是成立的。

遍历完后，计算出的 x 即为题目要求的值。

此算法只需要遍历一次 dinners 数组，时间复杂度为 O(n)；由于使用了辅助数组，其空间复杂度也为 O(n)。

---

代码实现

Java代码

import java.util.Scanner;
 
/**
 * 食堂供餐
 * 
 * @since 2023.09.13
 * @version 0.2
 * @author Frank
 *
 */
public class Dinners {
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			// 第一行输入就餐的批次
			String strCount = sc.nextLine();
			int count = Integer.parseInt(strCount);
			// 第二行输入初始库存数
			String strStockQty = sc.nextLine();
			int stockQty = Integer.parseInt(strStockQty);
			// 第三行输入每批次所需的午餐份数
			// 此处dinners中的元素都是String，后面需要转换成int处理
			String strDinners = sc.nextLine();
			String[] dinners = strDinners.split(" "); // dinners.length == count
 
			processDinners(count, stockQty, dinners);
		}
	}
 
	private static void processDinners(int count, int stockQty, String[] dinners) {
		int currentSumNeeded = 0;
		int x = 0;
		int currentStock = stockQty;
		for (int i = 0; i < count; i++) {
			currentStock = stockQty + i * x;
			currentSumNeeded += Integer.parseInt(dinners[i]);
			if (currentStock < currentSumNeeded) {
				// 计算最小的 x（新值必定比当前的x大），确保 currentStock >= currentSumNeeded
				int diff = currentSumNeeded - stockQty;
				int tmpX = diff / i;
				if (diff % i != 0) {
					tmpX++;
				}
				x = tmpX;
			}
		}
		System.out.println(x);
	}
}

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {
    while (line = await readline()) {
        // 第一行，进餐的批次
        var count = parseInt(line);
        // 第二行，初始库存数
        var strStockQty = await readline();
        var stockQty = parseInt(strStockQty);
        // 第三行，每批次需要的份数
        var initDinners = await readline();
        var strDinners = initDinners.split(" ");
 
        processDinners(count, stockQty, strDinners);
    }
}();
 
function processDinners(count, stockQty, strDinners) {
    var currentSumNeeded = 0;
    var x = 0;
    var currentStock = stockQty;
    for (var i = 0; i < count; i++) {
        currentStock = stockQty + i * x;
        currentSumNeeded += parseInt(strDinners[i]);
        if (currentStock < currentSumNeeded) {
            // 计算最小的 x（新值必定比当前的x大），确保 currentStock >= currentSumNeeded
            var diff = currentSumNeeded - stockQty;
            var tmpX = parseInt(diff / i);
            if (diff % i != 0) {
                tmpX++;
            }
            x = tmpX;
        }
    }
    console.log(x);
}

(完)