06-28 14:26 北京理工大学算法工程师发布于浙江

关注

最新华为OD机试真题-分月饼(200分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新 华为OD机试-D卷 的三语言AC题解

👏 感谢大家的订阅➕ 和喜欢💗

📎在线评测链接

=> 评测链接🔗 <=

华为OD

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

alt

🐢 分月饼

中秋节，公司要给员工分月饼。公司有 $m$ 个员工，买了 $n$ 个月饼，且 $m \le n$ 。每个员工至少分到 1 个月饼，但可以分多个。

要求：

单人分到最多的月饼个数为 $Max1$ ，单人分到第二多的月饼个数为 $Max2$ ，需要满足 $Max1 - Max2 \le 3$ 。
单人分到倒数第二多的月饼个数为 $Max(n-1)$ ，单人分到最少的月饼个数为 $Max(n)$ ，需要满足 $Max(n-1) - Max(n) \le 3$ 。

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

输入格式

第一行输入两个整数 $m$ 和 $n$ ，表示 $m$ 个员工和 $n$ 个月饼， $m \le n$ 。

输出格式

输出有多少种分月饼的方法。

样例输入

输入

2 4

输出

输入

3 5

输出

输入

3 12

输出

数据范围

$1 \le m \le n \le 100$

题解

题目要求计算满足条件的分月饼方法数。可以使用深度优先搜索（DFS）来遍历所有可能的分配方案，并统计满足条件的方案数。

参考代码

Python

def count_ways(m, n):
    def dfs(u, sum, down, up):
        nonlocal res
        if u == m:
            if sum == 0:
                res += 1
            return
        if sum < down or down > up:
            return
        for i in range(down, up + 1):
            dfs(u + 1, sum - i, i, min(sum - i, i + 3))

    res = 0
    dfs(0, n, 1, n)
    return res

if __name__ == "__main__":
    m, n = map(int, input().split())
    print(count_ways(m, n))

Java

import java.util.Scanner;

public class Main {
    static int n, m; // 月饼数，员工数
    static int res;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        m = in.nextInt();
        n = in.nextInt();
        dfs(0, n, 1, n);
        System.out.println(res);
    }

    static void dfs(int u, int sum, int down, int up) {
        if (u == m) {
            if (sum == 0) {
                res++;
            }
            return;
        }
        if (sum < down || down > up) {
            return;
        }
        for (int i = down; i <= up; i++) {
            dfs(u + 1, sum - i, i, Math.min(sum - i, i + 3));
        }
    }
}

#include <iostream>
using namespace std;

int res = 0;

void dfs(int u, int sum, int down, int up, int m) {
    if (u == m) {
        if (sum == 0) {
            res++;
        }
        return;
    }
    if (sum < down || down > up) {
        return;
    }
    for (int i = down; i <= up; i++) {
        dfs(u + 1, sum - i, i, min(sum - i, i + 3), m);
    }
}

int main() {
    int m, n;
    cin >> m >> n;
    dfs(0, n, 1, n, m);
    cout << res << endl;
    return 0;
}

(200分)59.分月饼

分月饼