华为OD机试真题---最短木板长度

华为OD机试中的“最短木板长度”问题是一个典型的算法问题，其问题描述及解法如下：

一、问题描述

小明有n块木板，每块木板的长度不同。现在小明买了一块长度为m的木料，这块木料可以切割成任意块，然后拼接到已有的木板上用来加长木板。小明的目标是让最短的木板长度尽可能长。问题要求计算加长木板后，最短木板的长度最大可以为多少。

输入：

• 第一行包含两个正整数n和m，n(1≤n≤10^3 ）、m(1≤m≤10^6)n表示木板数，m表示新买木料的长度。
• 第二行包含n个正整数，表示每块木板的初始长度，a1,a2…an(1≤ai≤10^6)

输出：

• 输出的唯一一行包含一个正整数，表示加长木板后，最短木板的长度最大可以为多少。

二、解题思路

1. 排序：将木板按长度从小到大排序，这样可以直接找到最短木板。

2. 迭代：每次迭代时，将剩余木料尽可能多地分配给当前最短的木板，使其长度增长。

   • 分配木料时，计算当前最短木板与最长木板之间的长度差，并判断剩余木料是否足够填补这一差距。
   • 如果剩余木料不足以填补差距，则将其全部用于增长最短木板。

3. 重新排序：每次增长最短木板后，都需要重新排序木板，以便在下次迭代时能够继续处理新的最短木板。

4. 迭代终止：当剩余木料为0时，表示所有木料都已用完，迭代终止。如果所有木板长度相等且剩余木料为0，也满足终止条件，因为此时所有木板长度已达到最大且无法再增长。

示例

输入：

5 3
4 5 3 5 5

输出：

5

三、代码实现

import java.util.Arrays;
import java.util.Scanner;public class ShortestBoardLength {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 从输入中读取木板数量n和新木料的长度mint n = scanner.nextInt();int m = scanner.nextInt();// 验证输入是否合法if (n <= 0 || m < 0) {System.out.println("Invalid input: n must be positive and m must be non-negative.");scanner.close();return;}// 读取并存储每块木板的初始长度int[] boards = new int[n];for (int i = 0; i < n; i++) {boards[i] = scanner.nextInt();if (boards[i] < 0) {System.out.println("Invalid input: board lengths must be non-negative.");scanner.close();return;}System.out.println(boards[i]);}// 对木板长度进行排序Arrays.sort(boards);// 使用贪心算法来尽可能增加最短木板的长度while (m > 0) {int diff = boards[n - 1] - boards[0]; // 计算最长木板与最短木板间的长度差if (m >= diff) {// 若剩余木料足够填补长度差，则直接填补for (int i = 0; i < n; i++) {if (boards[i] == boards[0]) {boards[i] += diff; // 增长最短木板的长度}}// 重新排序木板Arrays.sort(boards);m -= diff; // 减去已使用的木料长度} else {// 若剩余木料不足以填补长度差，则全部用于增长最短木板boards[0] += m; // 增长最短木板m = 0; // 剩余木料用完}}// 输出最终结果，即加长后最短木板的最大可能长度System.out.println("最短木板的最大可能长度:"+boards[0]);scanner.close();
}}

四、程序逻辑

1. 输入处理：程序首先读取两个整数 n 和 m，分别表示木板的数量和可用新木料的长度。然后读取 n 个整数，表示每块木板的初始长度。

2. 输入验证：程序检查输入的合法性，确保 n 是正数，m 是非负数，且所有木板的长度是非负数。

3. 排序：将所有木板的长度按升序排序。

4. 贪心算法：

   • 使用贪心策略，每次尽可能增加最短木板的长度。
   • 计算最长木板与最短木板之间的长度差 diff。
   • 如果剩余木料 m 足够填补这个长度差，则将所有最短木板的长度增加到最长木板的长度，并更新剩余木料 m。
   • 如果剩余木料 m 不足以填补长度差，则将最短木板增长 m 的长度，并将剩余木料 m 设为0。

5. 输出结果：最后输出加长后最短木板的最大可能长度。

五、运行示例解析

输入：

5 3
4 5 3 5 5

步骤：

1. 读取输入：

   • n = 5
   • m = 3
   • 木板长度数组：boards = [4, 5, 3, 5, 5]

2. 排序：

   • 排序后的木板长度数组：boards = [3, 4, 5, 5, 5]

3. 贪心算法：

   • 初始时，最短木板长度为 3，最长木板长度为 5，长度差 diff = 5 - 3 = 2。
   • 由于 m = 3 大于 diff = 2，可以填补长度差。
   • 将所有长度为 3 的木板增加到 5 的长度。
   • 更新后的木板长度数组：boards = [5, 4, 5, 5, 5]（注意，最短木板已增长，但排序已变，这里为了简化直接显示增长后的效果，实际代码中会重新排序）
   • 更新剩余木料：m = 3 - 2 = 1
   • 再次排序（实际上此步骤在这个特定情况下不是必需的，因为最短木板已增加到最长，但按算法逻辑，我们重新排序）：boards = [4, 5, 5, 5, 5]
   • 此时最短木板长度为 4，没有更多的最短木板可以增长（因为都已经是 5 了），且剩余木料 m = 1 不足以将任何木板从 4 增长到 5。
   • 因此，最终最短木板的最大可能长度为 4（在这个特定情况下，由于我们已经将所有木板增长到了 5 或以上，而剩余木料不足以进一步增长，所以最短长度保持不变，但这是因为我们之前已经增长了最短木板到最长）。不过，重要的是理解贪心算法的逻辑，即每次尽可能增长最短木板。

六、注意事项

注意：在给出的代码中，由于我们在每次增长最短木板后都重新排序，因此最终输出的最短木板长度是在所有增长操作后实际存在的最短长度，而不是在增长过程中的某个中间状态。在这个特定例子中，由于我们一开始就将最短木板增长到了最长木板的长度，并且剩余木料不足以进一步增长任何木板，所以最终输出的是增长后的最短长度（在这个例子中是 5，但如果我们严格按照贪心策略每次只处理最短木板且考虑剩余木料，那么在每次迭代后都重新评估最短木板，最终输出应为 4 的逻辑增长过程后的结果，但在这个特定输入下，所有木板最终都被增长到了 5 或以上，且由于剩余木料，没有木板保持在 4 的长度）。然而，基于代码逻辑和贪心策略的直接应用，如果我们严格按照每次增长最短木板并重新评估的逻辑，那么在处理完所有增长后，我们会找到最终的最短木板长度，考虑到输入示例和代码逻辑，这里的解释是为了帮助理解贪心策略的应用过程。在实际代码中，由于我们直接增长了最短木板到最长木板的长度（当木料足够时），所以最终输出的是增长后的统一长度。

修正：根据直接运行代码的结果，对于输入 5 3 4 5 3 5 5，代码会输出 5，因为所有木板都被增长到了至少 5 的长度，且剩余木料不足以进一步增长任何木板。这里的解释是为了帮助理解贪心算法的逻辑过程，而直接运行代码的结果是基于贪心策略的直接应用，即将最短木板增长到可能的最长长度（在这个例子中是所有木板都被增长到了 5）。