(C卷,200分)- 分月饼（Java & JS & Python & C）

题目描述

中秋节，公司分月饼，m 个员工，买了 n 个月饼，m ≤ n，每个员工至少分 1 个月饼，但可以分多个，

• 单人分到最多月饼的个数是 Max1 ，单人分到第二多月饼个数是 Max2 ，Max1 – Max2 ≤ 3 ，
• 单人分到第 n – 1 多月饼个数是 Max(n-1)，单人分到第n多月饼个数是 Max(n) ，Max(n-1) – Max(n) ≤ 3,

问有多少种分月饼的方法？

输入描述

每一行输入m n，表示m个员工，n个月饼，m ≤ n

输出描述

输出有多少种月饼分法

用例

题目解析

本题类似于整数划分问题，即将一个正整数n，分解为m个正整数的方案数。

这类问题一般不会有太大的数量级，比如将10000分解为10个整数，那方案数就太多了。

本题给了一个限制条件，那就是，如果将分解后的m个正整数升序的话，相邻元素之间的差值不能超过3。

另外，分解方案不在意m个正整数的顺序，比如 1 2 1 和 1 1 2算一种方案。

我这里考虑使用分治递归求解。

分治递归可以想象成一棵树，这颗树有m层。

第0层相当于序号0个员工，该层有多个节点，每个节点的值即为序号0个员工可能分得的月饼数量。

• 题目说，每个员工至少分得1个月饼，因此序号0个员工分得月饼数至少为1。
• 为了保证不产生重复方案，因此我们默认当前求解的升序的m个正整数序列，因此序号0个员工分得的月饼数不能超过均值，即 n / m，因为一旦序号0个员工分得的月饼超过均值，则其后面的员工必然会有分得小于均值月饼数的情况。

因此第0个员工分得的月饼数范围是 1 ~ n / m

接下来是第1层，相当于序号1员工，该员工分得的月饼数取决于上一层的员工：

• 为了保证升序，序号1员工分得的月饼最少数量即序号0员工分得的月饼数量
• 同时，题目限定相邻员工之间，月饼数差距不能超过3，因此序号1员工最多分得的月饼数量 = 序号0员工分得月饼数量 + 3
• 另外为了保证后面员工分得月饼数一定不小于序号1员工，因此序号1员工分得的月饼数量不能超过 (剩余月饼数量 ➗ 剩余员工数量) ，其中：

1. 剩余月饼数量 = n – 序号0员工分得的月饼数
2. 剩余员工数量  = m – 1

接下来层数同理，直到第m-1层，即分配到最后一个员工，此时最后一个员工将分得剩余所有月饼，如果最后一个员工和倒数第二个员工月饼数差距bu超过3，即可判断当前递归分支对应的分配方案可行与否

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const [m, n] = (await readline()).split(" ").map(Number);
  let ans = 0;

  /**
   *
   * @param {*} level 第几个员工
   * @param {*} min 当前员工至少分得几个月饼
   * @param {*} max 当前员工至多分得几个月饼
   * @param {*} remain 分月饼给当前员工前，月饼的剩余数量
   */
  function recursive(level, min, max, remain) {
    if (level == m - 1) {
      // 分到最后一个员工时，我们应该将剩余月饼都给他
      // 因此最后一个员工的月饼数量就是remain，而倒数第二个员工的月饼数量是min（本轮递归的min参数，即上一轮员工分得的月饼数量）
      // 如果二者差距不超过maxDiff，则分月饼方案可行
      if (remain - min <= 3) {
        ans++;
      }
      return;
    }

    // i 是当前员工可以分得的月饼数量
    for (let i = min; i <= max; i++) {
      remain -= i;
      // 下一个员工至少分得 i 个月饼（当前员工分得的月饼数量），至多分得 i + maxDiff
      // 同时下一个员工分得的月饼数量不能超过：均分月饼数量（即剩余月饼总数 / 剩余员工总数），否则破坏去重策略（为了保证分月饼的方案不重复，我们这里保证后面的员工分得月饼数不小于前面员工）
      recursive(
        level + 1,
        i,
        Math.min(i + 3, remain / (m - level - 1)),
        remain
      );
      remain += i;
    }
  }

  if (m == 1) {
    // 如果只有一个员工分月饼，那么就只有一种方案
    console.log(1);
  } else {
    // 如果有多个员工分月饼，为了保证分月饼的方案不重复，我们这里保证 员工i的月饼数量 <= 员工i+1的月饼数量
    // 因此对于第0个员工，至少分得1个月饼，至多分得n/m个月饼（均分数量）
    recursive(0, 1, n / m, n);
    console.log(ans);
  }
})();

Java算法源码

import java.util.Scanner;

public class Main {
  static int m;
  static int n;
  static int maxDiff = 3;
  static int ans = 0;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    m = sc.nextInt();
    n = sc.nextInt();

    if (m == 1) {
      // 如果只有一个员工分月饼，那么就只有一种方案
      System.out.println(1);
    } else {
      // 如果有多个员工分月饼，为了保证分月饼的方案不重复，我们这里保证 员工i的月饼数量 <= 员工i+1的月饼数量
      // 因此对于第0个员工，至少分得1个月饼，至多分得n/m个月饼（均分数量）
      recursive(0, 1, n / m, n);
      System.out.println(ans);
    }
  }

  /**
   * @param level 第几个员工
   * @param min 当前员工至少分得几个月饼
   * @param max 当前员工至多分得几个月饼
   * @param remain 分月饼给当前员工前，月饼的剩余数量
   */
  public static void recursive(int level, int min, int max, int remain) {
    if (level == m - 1) {
      // 分到最后一个员工时，我们应该将剩余月饼都给他
      // 因此最后一个员工的月饼数量就是remain，而倒数第二个员工的月饼数量是min（本轮递归的min参数，即上一轮员工分得的月饼数量）
      // 如果二者差距不超过maxDiff，则分月饼方案可行
      if (remain - min <= maxDiff) {
        ans++;
      }
      return;
    }

    // i 是当前员工可以分得的月饼数量
    for (int i = min; i <= max; i++) {
      // 下一个员工至少分得 i 个月饼（当前员工分得的月饼数量），至多分得 i + maxDiff
      // 同时下一个员工分得的月饼数量不能超过：均分月饼数量（即剩余月饼总数 / 剩余员工总数），否则破坏去重策略（为了保证分月饼的方案不重复，我们这里保证后面的员工分得月饼数不小于前面员工）
      remain -= i;
      recursive(level + 1, i, Math.min(i + maxDiff, remain / (m - level - 1)), remain);
      remain += i;
    }
  }
}

Python算法源码

# 输入获取
m, n = map(int, input().split())

ans = 0


# 递归
def recursive(level, low, high, remain):
    """
    :param level: 第几个员工
    :param low: 当前员工至少分得几个月饼
    :param high: 当前员工至多分得几个月饼
    :param remain: 分月饼给当前员工前，月饼的剩余数量
    """
    global ans

    # 分到最后一个员工时，我们应该将剩余月饼都给他
    if level == m - 1:
        # 因此最后一个员工的月饼数量就是remain，而倒数第二个员工的月饼数量是low（本轮递归的min参数，即上一轮员工分得的月饼数量）
        if remain - low <= 3:
            # 如果二者差距不超过maxDiff，则分月饼方案可行
            ans += 1

        return

    # i 是当前员工可以分得的月饼数量
    for i in range(low, high + 1):
        remain -= i
        # 下一个员工至少分得 i 个月饼（当前员工分得的月饼数量），至多分得 i + maxDiff
        # 同时下一个员工分得的月饼数量不能超过：均分月饼数量（即剩余月饼总数 / 剩余员工总数），否则破坏去重策略（为了保证分月饼的方案不重复，我们这里保证后面的员工分得月饼数不小于前面员工）
        recursive(level + 1, i, min(i + 3, remain // (m - level - 1)), remain)
        remain += i


# 算法入口
def getResult():
    if m == 1:
        # 如果只有一个员工分月饼，那么就只有一种方案
        return 1
    else:
        # 如果有多个员工分月饼，为了保证分月饼的方案不重复，我们这里保证 员工i的月饼数量 <= 员工i+1的月饼数量
        # 因此对于第0个员工，至少分得1个月饼，至多分得n/m个月饼（均分数量）
        recursive(0, 1, n // m, n)
        return ans


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>

#define MIN(a, b) ((a) < (b) ? (a) : (b))

#define MAX_DIFF 3

int m, n;
int ans = 0;

/*!
 *
 * @param level 第几个员工
 * @param min 当前员工至少分得几个月饼
 * @param max 当前员工至多分得几个月饼
 * @param remain 分月饼给当前员工前，月饼的剩余数量
 */
void recursive(int level, int min, int max, int remain) {
    // 分到最后一个员工时，我们应该将剩余月饼都给他
    if (level == m - 1) {
        // 因此最后一个员工的月饼数量就是remain，而倒数第二个员工的月饼数量是min（本轮递归的min参数，即上一轮员工分得的月饼数量）
        if (remain - min <= MAX_DIFF) {
            // 如果二者差距不超过maxDiff，则分月饼方案可行
            ans++;
        }
        return;
    }

    // i 是当前员工可以分得的月饼数量
    for (int i = min; i <= max; i++) {
        remain -= i;
        // 下一个员工至少分得 i 个月饼（当前员工分得的月饼数量），至多分得 i + maxDiff
        // 同时下一个员工分得的月饼数量不能超过：均分月饼数量（即剩余月饼总数 / 剩余员工总数），否则破坏去重策略（为了保证分月饼的方案不重复，我们这里保证后面的员工分得月饼数不小于前面员工）
        recursive(level + 1, i, MIN(i + MAX_DIFF, remain / (m - level - 1)), remain);
        remain += i;
    }
}

int main() {

    scanf("%d %d", &m, &n);

    if (m == 1) {
        // 如果只有一个员工分月饼，那么就只有一种方案
        puts("1");
    } else {
        // 如果有多个员工分月饼，为了保证分月饼的方案不重复，我们这里保证 员工i的月饼数量 <= 员工i+1的月饼数量
        // 因此对于第0个员工，至少分得1个月饼，至多分得n/m个月饼（均分数量）
        recursive(0, 1, n / m, n);
        printf("%dn", ans);
    }
}