(A卷,100分)- 等和子数组最小和（Java & JS & Python）

题目描述

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

输入描述

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

输出描述

最小拆分数组和

用例

题目解析

本题算是

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

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

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

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

而验证nums是否可以划分为k层，其实就是判断nums是否可以划分为k个和相等的子集，这个判断逻辑可以复用LeetCode – 698 划分为k个相等的子集_伏城之外的博客-CSDN博客

中的逻辑。

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算法源码

感谢m0_71826536指正41行错误，41行在用例

5

5 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();

    LinkedList<Integer> link = new LinkedList<>();
    for (int i = 0; i < m; i++) {
      link.add(sc.nextInt());
    }

    System.out.println(getResult(link, m));
  }

  public static int getResult(LinkedList<Integer> link, int m) {
    link.sort((a, b) -> b - a);

    int sum = 0;
    for (Integer ele : link) {
      sum += ele;
    }

    while (m > 0) {
      LinkedList<Integer> link_cp = new LinkedList<>(link);
      if (canPartitionMSubsets(link_cp, sum, m)) return sum / m;
      m--;
    }

    return sum;
  }

  public static boolean canPartitionMSubsets(LinkedList<Integer> 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(LinkedList<Integer> 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(reverse=True)

    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))