(100分)- 等和子数组最小和Java JS Python题目描述给定一个数组nums将元素分为若干个组使得每组和相等求出满足条件的所有分组中组内元素和的最小值。输入描述第一行输入 m接着输入m个数表示此数组nums数据范围1m50, 1nums[i]50输出描述最小拆分数组和用例输入74 3 2 3 5 2 1输出5说明可以等分的情况有4 个子集51,42,32,32 个子集5, 1, 42,3, 2,3但最小的为5。题目解析题目要求我们求解最小拆分数组和本质上就是寻找最小子集和也就是确定最大的k值。因为k值越大对应的子集和就越小。k值的求解思路如下首先考虑k的上限。当数组所有元素相等时k等于数组长度m即每个元素都能独立构成一个子集。因此可以从km开始尝试。如果km不满足条件就逐步减小k值k--直到k1为止。验证数组能否划分为k个和相等的子集就是判断nums是否能分成k个等和子集。JavaScript算法源码/* JavaScript Node ACM模式 控制台输入获取 */ const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines []; rl.on(line, (line) { lines.push(line); if (lines.length 2) { const m parseInt(lines[0]); const arr lines[1].split( ).map(Number); console.log(getResult(arr, m)); lines.length 0; } }); function getResult(arr, m) { const sum arr.sort((a, b) b - a).reduce((p, c) p c); while (m) { if (canPartitionMSubsets([...arr], sum, m)) return sum / m; m--; } return sum; } function canPartitionMSubsets(arr, sum, m) { if (sum % m ! 0) return false; const subSum sum / m; if (subSum arr[0]) return false; while (arr[0] subSum) { arr.shift(); m--; } const buckets new Array(m).fill(0); return partition(arr, 0, buckets, subSum); } function partition(arr, index, buckets, subSum) { if (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; } } return false; }Java算法源码41行在用例55 5 5 5 5时会出现越界异常import java.util.LinkedList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int m sc.nextInt(); LinkedListInteger link new LinkedList(); for (int i 0; i m; i) { link.add(sc.nextInt()); } System.out.println(getResult(link, m)); } public static int getResult(LinkedListInteger link, int m) { link.sort((a, b) - b - a); int sum 0; for (Integer ele : link) { sum ele; } while (m 0) { LinkedListInteger link_cp new LinkedList(link); if (canPartitionMSubsets(link_cp, sum, m)) return sum / m; m--; } return sum; } public static boolean canPartitionMSubsets(LinkedListInteger link, int sum, int m) { if (sum % m ! 0) return false; int subSum sum / m; if (subSum link.get(0)) return false; // while (link.get(0) subSum) { // 此段代码可能越界 while (link.size() 0 link.get(0) subSum) { link.removeFirst(); m--; } int[] buckets new int[m]; return partition(link, 0, buckets, subSum); } public static boolean partition(LinkedListInteger link, int index, int[] buckets, int subSum) { if (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; } } return false; } }Python算法源码# 输入获取 m int(input()) link list(map(int, input().split())) # 算法入口 def getResult(link, m): link.sort(reverseTrue) sumV 0 for ele in link: sumV ele while m 0: if canPartitionMSubsets(link[:], sumV, m): return int(sumV / m) m - 1 return sumV def canPartitionMSubsets(link, sumV, 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 buckets [0] * m return partition(link, 0, buckets, subSum) def partition(link, index, buckets, subSum): if 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 True buckets[i] - select return False # 算法调用 print(getResult(link, m))