【2024年华为OD机试】(A卷,100分)- 等和子数组最小和（Java JS PythonC/C++）

在这里插入图片描述

一、问题描述

题目描述

给定一个数组nums，将元素分为若干个组，使得每组和相等，求出满足条件的所有分组中，组内元素和的最小值。

输入描述

第一行输入 m
接着输入m个数，表示此数组nums
数据范围：1<=m<=50, 1<=nums[i]<=50

输出描述

最小拆分数组和

用例

输入

7
4 3 2 3 5 2 1

输出

说明

可以等分的情况有：

4 个子集（5），（1,4），（2,3），（2,3）
2 个子集（5, 1, 4），（2,3, 2,3）

但最小的为5。

题目解析

本题算是划分为k个相等的子集的变种题，本题同样是要将数组划分为k个和相等的子集。

本题要我们求解：最小拆分数组和，其实就是求解：最小子集和，其实就是求解，最大k值。因为k值越大，则对应的子集的和越小。

这里k的求解很简单，首先，我们可以猜想下k的上限是多少？

比如数组所有元素都相等，则k === m，即每个元素都能作为一个子集，因此我们可以让k从m开始尝试，如果不行，则k–，直到k=1。

而验证nums是否可以划分为k层，其实就是判断nums是否可以划分为k个和相等的子集，这个判断逻辑可以复用划分为k个相等的子集中的逻辑。

二、JavaScript算法源码

以下是对提供的 JavaScript 代码的中文详细注释和逻辑讲解：

JavaScript 代码实现

javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");// 创建 readline 接口，用于从控制台读取输入
const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});// 存储输入行的数组
const lines = [];// 监听每一行输入
rl.on("line", (line) => {lines.push(line); // 将输入行存入 lines 数组// 当输入行数为 2 时，表示输入完成if (lines.length === 2) {const m = parseInt(lines[0]); // 解析第一行输入，获取 m 的值const arr = lines[1].split(" ").map(Number); // 解析第二行输入，获取数组 arr// 调用 getResult 函数计算结果并输出console.log(getResult(arr, m));// 清空 lines 数组，准备接收下一组输入lines.length = 0;}
});/*** 计算将数组划分为 m 个子集的最大子集和* @param {number[]} arr - 输入的数组* @param {number} m - 子集的数量* @returns {number} - 最大子集和*/
function getResult(arr, m) {// 对数组进行降序排序const sum = arr.sort((a, b) => b - a).reduce((p, c) => p + c);// 从 m 开始递减，尝试将数组划分为 m 个子集while (m) {// 如果可以将数组划分为 m 个子集，返回子集和if (canPartitionMSubsets([...arr], sum, m)) return sum / m;m--;}// 如果无法划分，返回数组总和return sum;
}/*** 判断是否可以将数组划分为 m 个子集，每个子集的和为 subSum* @param {number[]} arr - 输入的数组* @param {number} sum - 数组的总和* @param {number} m - 子集的数量* @returns {boolean} - 是否可以划分*/
function canPartitionMSubsets(arr, sum, m) {// 如果总和不能被 m 整除，无法划分if (sum % m !== 0) return false;// 计算每个子集的目标和const subSum = sum / m;// 如果数组中的最大值大于目标和，无法划分if (subSum < arr[0]) return false;// 如果数组中的某个元素等于目标和，直接将其作为一个子集while (arr[0] === subSum) {arr.shift(); // 移除该元素m--; // 减少子集数量}// 初始化 m 个桶，用于存储每个子集的当前和const buckets = new Array(m).fill(0);// 调用 partition 函数进行递归划分return partition(arr, 0, buckets, subSum);
}/*** 递归尝试将数组划分为 m 个子集* @param {number[]} arr - 输入的数组* @param {number} index - 当前处理的数组索引* @param {number[]} buckets - 存储每个子集当前和的数组* @param {number} subSum - 每个子集的目标和* @returns {boolean} - 是否可以划分*/
function partition(arr, index, buckets, subSum) {// 如果所有元素都已处理，返回 trueif (index === arr.length) return true;// 获取当前处理的元素const select = arr[index];// 尝试将当前元素放入每个桶中for (let i = 0; i < buckets.length; i++) {// 如果当前桶和前一个桶的和相同，跳过（避免重复计算）if (i > 0 && buckets[i] === buckets[i - 1]) continue;// 如果当前元素可以放入当前桶if (select + buckets[i] <= subSum) {buckets[i] += select; // 将当前元素放入桶中// 递归处理下一个元素if (partition(arr, index + 1, buckets, subSum)) return true;buckets[i] -= select; // 回溯：将当前元素从桶中移除}}// 如果无法放入任何桶，返回 falsereturn false;
}

代码讲解

1. 输入处理

使用 readline 模块从控制台读取输入。
将输入的两行数据分别解析为 m（子集数量）和 arr（数组）。
当输入完成后，调用 getResult 函数计算结果并输出。

2. 主逻辑：`getResult` 函数

对数组进行降序排序，并计算数组的总和 sum。
从 m 开始递减，尝试将数组划分为 m 个子集。
如果成功划分，返回子集和 sum / m；否则返回数组总和 sum。

3. 判断是否可以划分：`canPartitionMSubsets` 函数

检查总和 sum 是否能被 m 整除，如果不能，直接返回 false。
计算每个子集的目标和 subSum。
如果数组中的最大值大于 subSum，无法划分，返回 false。
如果数组中的某个元素等于 subSum，直接将其作为一个子集，并减少子集数量 m。
初始化 m 个桶，调用 partition 函数进行递归划分。

4. 递归划分：`partition` 函数

如果所有元素都已处理，返回 true。
尝试将当前元素放入每个桶中：
- 如果当前桶和前一个桶的和相同，跳过（避免重复计算）。
- 如果当前元素可以放入当前桶，递归处理下一个元素。
- 如果无法放入任何桶，返回 false。

示例解析

输入

3
4 3 2 3 5 2 1

运行结果

解析：
- 数组 [4, 3, 2, 3, 5, 2, 1] 的总和为 20。
- 尝试划分为 3 个子集，目标和为 20 / 3 ≈ 6.67，无法整除。
- 尝试划分为 2 个子集，目标和为 10，可以划分为 [5, 4, 1] 和 [3, 3, 2, 2]。
- 返回最大子集和 5。

总结

该代码通过递归和回溯的方式，尝试将数组划分为 m 个子集。
使用降序排序和剪枝优化，提高了算法效率。
代码逻辑清晰，适用于解决类似划分问题的场景。

如果有其他问题，欢迎随时提问！

三、Java算法源码

以下是对提供的 Java 代码的中文详细注释和逻辑讲解，同时修复了越界异常问题：

Java 代码实现

java">import java.util.LinkedList;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 读取子集数量 mint m = sc.nextInt();// 创建链表存储数组元素LinkedList<Integer> link = new LinkedList<>();for (int i = 0; i < m; i++) {link.add(sc.nextInt()); // 读取数组元素并添加到链表中}// 调用 getResult 函数计算结果并输出System.out.println(getResult(link, m));}/*** 计算将数组划分为 m 个子集的最大子集和* @param link - 输入的链表* @param m - 子集的数量* @return - 最大子集和*/public static int getResult(LinkedList<Integer> link, int m) {// 对链表进行降序排序link.sort((a, b) -> b - a);// 计算链表元素的总和int sum = 0;for (Integer ele : link) {sum += ele;}// 从 m 开始递减，尝试将数组划分为 m 个子集while (m > 0) {// 创建链表的副本，避免修改原链表LinkedList<Integer> link_cp = new LinkedList<>(link);// 如果可以将数组划分为 m 个子集，返回子集和if (canPartitionMSubsets(link_cp, sum, m)) return sum / m;m--;}// 如果无法划分，返回数组总和return sum;}/*** 判断是否可以将数组划分为 m 个子集，每个子集的和为 subSum* @param link - 输入的链表* @param sum - 数组的总和* @param m - 子集的数量* @return - 是否可以划分*/public static boolean canPartitionMSubsets(LinkedList<Integer> link, int sum, int m) {// 如果总和不能被 m 整除，无法划分if (sum % m != 0) return false;// 计算每个子集的目标和int subSum = sum / m;// 如果数组中的最大值大于目标和，无法划分if (subSum < link.get(0)) return false;// 如果数组中的某个元素等于目标和，直接将其作为一个子集// 修复越界异常：增加链表非空检查while (link.size() > 0 && link.get(0) == subSum) {link.removeFirst(); // 移除该元素m--; // 减少子集数量}// 初始化 m 个桶，用于存储每个子集的当前和int[] buckets = new int[m];// 调用 partition 函数进行递归划分return partition(link, 0, buckets, subSum);}/*** 递归尝试将数组划分为 m 个子集* @param link - 输入的链表* @param index - 当前处理的链表索引* @param buckets - 存储每个子集当前和的数组* @param subSum - 每个子集的目标和* @return - 是否可以划分*/public static boolean partition(LinkedList<Integer> link, int index, int[] buckets, int subSum) {// 如果所有元素都已处理，返回 trueif (index == link.size()) return true;// 获取当前处理的元素int select = link.get(index);// 尝试将当前元素放入每个桶中for (int i = 0; i < buckets.length; i++) {// 如果当前桶和前一个桶的和相同，跳过（避免重复计算）if (i > 0 && buckets[i] == buckets[i - 1]) continue;// 如果当前元素可以放入当前桶if (select + buckets[i] <= subSum) {buckets[i] += select; // 将当前元素放入桶中// 递归处理下一个元素if (partition(link, index + 1, buckets, subSum)) return true;buckets[i] -= select; // 回溯：将当前元素从桶中移除}}// 如果无法放入任何桶，返回 falsereturn false;}
}

代码讲解

1. 输入处理

使用 Scanner 从控制台读取输入。
读取子集数量 m 和数组元素，并存储在 LinkedList 中。

2. 主逻辑：`getResult` 函数

对链表进行降序排序，并计算链表元素的总和 sum。
从 m 开始递减，尝试将数组划分为 m 个子集。
如果成功划分，返回子集和 sum / m；否则返回数组总和 sum。

3. 判断是否可以划分：`canPartitionMSubsets` 函数

检查总和 sum 是否能被 m 整除，如果不能，直接返回 false。
计算每个子集的目标和 subSum。
如果数组中的最大值大于 subSum，无法划分，返回 false。
如果数组中的某个元素等于 subSum，直接将其作为一个子集，并减少子集数量 m。
初始化 m 个桶，调用 partition 函数进行递归划分。

4. 递归划分：`partition` 函数

如果所有元素都已处理，返回 true。
尝试将当前元素放入每个桶中：
- 如果当前桶和前一个桶的和相同，跳过（避免重复计算）。
- 如果当前元素可以放入当前桶，递归处理下一个元素。
- 如果无法放入任何桶，返回 false。

修复越界异常

在 canPartitionMSubsets 函数中，修复了以下代码的越界异常：

java">while (link.get(0) == subSum) { // 原代码可能越界

修改为：

java">while (link.size() > 0 && link.get(0) == subSum) { // 增加链表非空检查

示例解析

输入

5
5 5 5 5 5

运行结果

解析：
- 数组 [5, 5, 5, 5, 5] 的总和为 25。
- 尝试划分为 5 个子集，目标和为 5，可以划分为 [5], [5], [5], [5], [5]。
- 返回最大子集和 5。

总结

该代码通过递归和回溯的方式，尝试将数组划分为 m 个子集。
修复了越界异常问题，确保代码的健壮性。
代码逻辑清晰，适用于解决类似划分问题的场景。

如果有其他问题，欢迎随时提问！

四、Python算法源码

以下是对提供的 Python 代码的中文详细注释和逻辑讲解：

Python 代码实现

python"># 输入获取
m = int(input())  # 读取子集数量 m
link = list(map(int, input().split()))  # 读取数组元素并存储在列表中# 算法入口
def getResult(link, m):# 对数组进行降序排序link.sort(reverse=True)# 计算数组元素的总和sumV = 0for ele in link:sumV += ele# 从 m 开始递减，尝试将数组划分为 m 个子集while m > 0:# 创建数组的副本，避免修改原数组if canPartitionMSubsets(link[:], sumV, m):return int(sumV / m)  # 如果成功划分，返回子集和m -= 1# 如果无法划分，返回数组总和return sumVdef canPartitionMSubsets(link, sumV, m):# 如果总和不能被 m 整除，无法划分if sumV % m != 0:return False# 计算每个子集的目标和subSum = sumV / m# 如果数组中的最大值大于目标和，无法划分if subSum < link[0]:return False# 如果数组中的某个元素等于目标和，直接将其作为一个子集while len(link) > 0 and link[0] == subSum:link.pop(0)  # 移除该元素m -= 1  # 减少子集数量# 初始化 m 个桶，用于存储每个子集的当前和buckets = [0] * m# 调用 partition 函数进行递归划分return partition(link, 0, buckets, subSum)def partition(link, index, buckets, subSum):# 如果所有元素都已处理，返回 Trueif index == len(link):return True# 获取当前处理的元素select = link[index]# 尝试将当前元素放入每个桶中for i in range(len(buckets)):# 如果当前桶和前一个桶的和相同，跳过（避免重复计算）if i > 0 and buckets[i] == buckets[i - 1]:continue# 如果当前元素可以放入当前桶if select + buckets[i] <= subSum:buckets[i] += select  # 将当前元素放入桶中# 递归处理下一个元素if partition(link, index + 1, buckets, subSum):return Truebuckets[i] -= select  # 回溯：将当前元素从桶中移除# 如果无法放入任何桶，返回 Falsereturn False# 算法调用
print(getResult(link, m))

代码讲解

1. 输入处理

使用 input() 函数从控制台读取输入。
读取子集数量 m 和数组元素，并存储在列表 link 中。

2. 主逻辑：`getResult` 函数

对数组进行降序排序，并计算数组元素的总和 sumV。
从 m 开始递减，尝试将数组划分为 m 个子集。
如果成功划分，返回子集和 sumV / m；否则返回数组总和 sumV。

3. 判断是否可以划分：`canPartitionMSubsets` 函数

检查总和 sumV 是否能被 m 整除，如果不能，直接返回 False。
计算每个子集的目标和 subSum。
如果数组中的最大值大于 subSum，无法划分，返回 False。
如果数组中的某个元素等于 subSum，直接将其作为一个子集，并减少子集数量 m。
初始化 m 个桶，调用 partition 函数进行递归划分。

4. 递归划分：`partition` 函数

如果所有元素都已处理，返回 True。
尝试将当前元素放入每个桶中：
- 如果当前桶和前一个桶的和相同，跳过（避免重复计算）。
- 如果当前元素可以放入当前桶，递归处理下一个元素。
- 如果无法放入任何桶，返回 False。

示例解析

输入

5
5 5 5 5 5

运行结果

解析：
- 数组 [5, 5, 5, 5, 5] 的总和为 25。
- 尝试划分为 5 个子集，目标和为 5，可以划分为 [5], [5], [5], [5], [5]。
- 返回最大子集和 5。

总结

该代码通过递归和回溯的方式，尝试将数组划分为 m 个子集。
使用降序排序和剪枝优化，提高了算法效率。
代码逻辑清晰，适用于解决类似划分问题的场景。

如果有其他问题，欢迎随时提问！

五、C/C++算法源码：

以下是为 C++ 代码的实现，并附上详细的中文注释和逻辑讲解：

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;// 判断是否可以将数组划分为 m 个子集
bool partition(vector<int>& link, int index, vector<int>& buckets, int subSum);// 判断是否可以将数组划分为 m 个子集，每个子集的和为 subSum
bool canPartitionMSubsets(vector<int> link, int sumV, int m) {// 如果总和不能被 m 整除，无法划分if (sumV % m != 0) return false;// 计算每个子集的目标和int subSum = sumV / m;// 如果数组中的最大值大于目标和，无法划分if (subSum < link[0]) return false;// 如果数组中的某个元素等于目标和，直接将其作为一个子集while (!link.empty() && link[0] == subSum) {link.erase(link.begin()); // 移除该元素m--; // 减少子集数量}// 初始化 m 个桶，用于存储每个子集的当前和vector<int> buckets(m, 0);// 调用 partition 函数进行递归划分return partition(link, 0, buckets, subSum);
}// 递归尝试将数组划分为 m 个子集
bool partition(vector<int>& link, int index, vector<int>& buckets, int subSum) {// 如果所有元素都已处理，返回 trueif (index == link.size()) return true;// 获取当前处理的元素int select = link[index];// 尝试将当前元素放入每个桶中for (int i = 0; i < buckets.size(); i++) {// 如果当前桶和前一个桶的和相同，跳过（避免重复计算）if (i > 0 && buckets[i] == buckets[i - 1]) continue;// 如果当前元素可以放入当前桶if (select + buckets[i] <= subSum) {buckets[i] += select; // 将当前元素放入桶中// 递归处理下一个元素if (partition(link, index + 1, buckets, subSum)) return true;buckets[i] -= select; // 回溯：将当前元素从桶中移除}}// 如果无法放入任何桶，返回 falsereturn false;
}// 算法入口
int getResult(vector<int>& link, int m) {// 对数组进行降序排序sort(link.begin(), link.end(), greater<int>());// 计算数组元素的总和int sumV = 0;for (int ele : link) {sumV += ele;}// 从 m 开始递减，尝试将数组划分为 m 个子集while (m > 0) {// 创建数组的副本，避免修改原数组if (canPartitionMSubsets(link, sumV, m)) {return sumV / m; // 如果成功划分，返回子集和}m--;}// 如果无法划分，返回数组总和return sumV;
}int main() {// 输入获取int m;cin >> m; // 读取子集数量 mvector<int> link;int num;while (cin >> num) {link.push_back(num); // 读取数组元素并存储在 vector 中if (cin.get() == '\n') break; // 如果遇到换行符，结束输入}// 算法调用cout << getResult(link, m) << endl;return 0;
}

代码讲解

1. 输入处理

使用 cin 从控制台读取输入。
读取子集数量 m 和数组元素，并存储在 vector<int> link 中。

2. 主逻辑：`getResult` 函数

对数组进行降序排序，并计算数组元素的总和 sumV。
从 m 开始递减，尝试将数组划分为 m 个子集。
如果成功划分，返回子集和 sumV / m；否则返回数组总和 sumV。

3. 判断是否可以划分：`canPartitionMSubsets` 函数

检查总和 sumV 是否能被 m 整除，如果不能，直接返回 false。
计算每个子集的目标和 subSum。
如果数组中的最大值大于 subSum，无法划分，返回 false。
如果数组中的某个元素等于 subSum，直接将其作为一个子集，并减少子集数量 m。
初始化 m 个桶，调用 partition 函数进行递归划分。

4. 递归划分：`partition` 函数

如果所有元素都已处理，返回 true。
尝试将当前元素放入每个桶中：
- 如果当前桶和前一个桶的和相同，跳过（避免重复计算）。
- 如果当前元素可以放入当前桶，递归处理下一个元素。
- 如果无法放入任何桶，返回 false。

示例解析

输入

5
5 5 5 5 5

运行结果

解析：
- 数组 [5, 5, 5, 5, 5] 的总和为 25。
- 尝试划分为 5 个子集，目标和为 5，可以划分为 [5], [5], [5], [5], [5]。
- 返回最大子集和 5。

总结

该代码通过递归和回溯的方式，尝试将数组划分为 m 个子集。
使用降序排序和剪枝优化，提高了算法效率。
代码逻辑清晰，适用于解决类似划分问题的场景。

如果有其他问题，欢迎随时提问！