返回目录

题目描述

中秋节，公司分月饼，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算一种方案。

Python算法源码

solutions = 0
MAX_DIFF = 3

# 递归函数：将月份分配给员工
def distribute_months(employee_index, min_months, max_months, remaining_months, total_employees):
    global solutions
  
    # 如果是最后一个员工，将所有剩余月份分配给他们
    if employee_index == total_employees - 1:
        # 如果剩余月份与 min_months 的差小于或等于 MAX_DIFF，则是一个有效解决方案
        if remaining_months - min_months <= MAX_DIFF:
            solutions += 1
        return

    # 将月份分配给当前员工
    i = min_months
    while i <= max_months:
        remaining_months -= i
        # 计算下一个员工的月份范围
        next_min = i
        next_max = min(i + MAX_DIFF, remaining_months // (total_employees - employee_index - 1))
        # 递归地将月份分配给下一个员工
        distribute_months(employee_index + 1, next_min, next_max, remaining_months, total_employees)
        remaining_months += i
        i += 1

# 主函数
def main():
    global solutions
    total_employees, total_months = map(int, input().split())

    if total_employees == 1:
        # 如果只有一个员工，那么只有一个解决方案
        print("1")
    else:
        # 开始将月份分配给员工
        # 对于每个员工，他们可以获得的最少月份为 1，最多为平均值（总月份 / 总员工数）
        distribute_months(0, 1, total_months // total_employees, total_months, total_employees)
        print(solutions)

if __name__ == "__main__":
    main()

C算法源码

#include <stdio.h>

int totalMonths, totalEmployees;
int solutions = 0;
const int MAX_DIFF = 3;

// 递归函数：将月份分配给员工
void distributeMonths(int employeeIndex, int minMonths, int maxMonths, int remainingMonths) {
    // 如果是最后一个员工，将所有剩余月份分配给他们
    if (employeeIndex == totalEmployees - 1) {
        // 如果剩余月份与 minMonths 的差小于或等于 MAX_DIFF，则是一个有效解决方案
        if (remainingMonths - minMonths <= MAX_DIFF) {
            solutions++;
        }
        return;
    }

    // 将月份分配给当前员工
    int i = minMonths;
    while (i <= maxMonths) {
        remainingMonths -= i;
        // 计算下一个员工的月份范围
        int nextMin = i;
        int nextMax = (i + MAX_DIFF) < (remainingMonths / (totalEmployees - employeeIndex - 1)) ? (i + MAX_DIFF) : (remainingMonths / (totalEmployees - employeeIndex - 1));
        // 递归地将月份分配给下一个员工
        distributeMonths(employeeIndex + 1, nextMin, nextMax, remainingMonths);
        remainingMonths += i;
        i++;
    }
}

// 主函数
int main() {
    int i;
    scanf("%d %d", &totalEmployees, &totalMonths);

    if (totalEmployees == 1) {
        // 如果只有一个员工，那么只有一个解决方案
        printf("1\n");
    } else {
        // 开始将月份分配给员工
        // 对于每个员工，他们可以获得的最少月份为 1，最多为平均值（总月份 / 总员工数）
        distributeMonths(0, 1, totalMonths / totalEmployees, totalMonths);
        printf("%d\n", solutions);
    }

    return 0;
}

Java算法源码

import java.util.Scanner;

public class Main {

    static int totalMonths, totalEmployees;
    static int solutions = 0;
    static final int MAX_DIFF = 3;

    // 递归函数：将月份分配给员工
    static void distributeMonths(int employeeIndex, int minMonths, int maxMonths, int remainingMonths) {
        // 如果是最后一个员工，将所有剩余月份分配给他们
        if (employeeIndex == totalEmployees - 1) {
            // 如果剩余月份与 minMonths 的差小于或等于 MAX_DIFF，则是一个有效解决方案
            if (remainingMonths - minMonths <= MAX_DIFF) {
                solutions++;
            }
            return;
        }

        // 将月份分配给当前员工
        int i = minMonths;
        while (i <= maxMonths) {
            remainingMonths -= i;
            // 计算下一个员工的月份范围
            int nextMin = i;
            int nextMax = Math.min(i + MAX_DIFF, remainingMonths / (totalEmployees - employeeIndex - 1));
            // 递归地将月份分配给下一个员工
            distributeMonths(employeeIndex + 1, nextMin, nextMax, remainingMonths);
            remainingMonths += i;
            i++;
        }
    }

    // 主函数
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        totalEmployees = scanner.nextInt();
        totalMonths = scanner.nextInt();

        if (totalEmployees == 1) {
            // 如果只有一个员工，那么只有一个解决方案
            System.out.println("1");
        } else {
            // 开始将月份分配给员工
            // 对于每个员工，他们可以获得的最少月份为 1，最多为平均值（总月份 / 总员工数）
            distributeMonths(0, 1, totalMonths / totalEmployees, totalMonths);
            System.out.println(solutions);
        }
    }
}