华为机试 - 最大平分数组

目录

题目描述

输入描述

输出描述

用例

题目解析

算法源码

---

题目描述

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

输入描述

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

输出描述

最大的平分组数个数

用例

题目解析

本题和

华为机试 - 叠积木_伏城之外的博客-CSDN博客_叠积木 算法

华为机试 - 等和子数组最小和_伏城之外的博客-CSDN博客

属于类似，解题步骤基本相同。

题解请看叠积木。

算法源码

/* 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 = lines[0] - 0;
    const arr = lines[1].split(" ").map(Number);

    console.log(getResutlt(m, arr));

    lines.length = 0;
  }
});

function getResutlt(m, arr) {
  const sum = arr.sort((a, b) => b - a).reduce((p, c) => p + c);

  let maxCount = m;

  while (maxCount >= 1) {
    if (canPartition(arr, sum, maxCount)) {
      return maxCount;
    } else {
      maxCount--;
    }
  }
}

function canPartition(arr, sum, maxCount) {
  if (sum % maxCount) return false;

  const subSum = sum / maxCount;

  if (subSum < arr[0]) return false;

  while (arr[0] === subSum) {
    arr.shift();
    maxCount--;
  }

  const buckets = new Array(maxCount).fill(0);

  return partition(0, arr, subSum, buckets);
}

function partition(start, arr, subSum, buckets) {
  if (start === arr.length) return true;

  const select = arr[start];

  for (let i = 0; i < buckets.length; i++) {
    if (i > 0 && buckets[i] === buckets[i - 1]) continue;

    if (buckets[i] + select <= subSum) {
      buckets[i] += select;
      if (partition(start + 1, arr, subSum, buckets)) return true;
      buckets[i] -= select;
    }
  }

  return false;
}