题解 | #给3个组员分配任务#

题目链接

给3个组员分配任务

题目描述

给定四个正整数 $n, x, y, z$ 。需要将 $n$ 个任务分配给三位员工（小v、小i、小o），他们能处理的任务上限分别为 $x, y, z$ 。要求计算出所有满足条件的分配方案总数。

一个分配方案指的是一个三元组 $(v, i, o)$ ，其中 $v, i, o$ 分别是分配给三位员工的任务数，需要满足以下条件：

$v + i + o = n$
$0 \le v \le x$
$0 \le i \le y$
$0 \le o \le z$

解题思路

这是一个简单的组合计数问题。由于所有输入的数值范围都非常小（最大为50），我们可以使用最直观的方法——暴力枚举来解决。

思路是固定其中两位员工的任务数，然后计算出第三位员工需要承担的任务数，最后检查这个分配方案是否满足所有约束条件。

具体算法步骤如下：

我们用两层循环来枚举分配给小v（任务数 $v$ ）和小i（任务数 $i$ ）的所有可能情况。
小v的任务数 $v$ 可以从 $0$ 取到他的上限 $x$ ，同时不能超过总任务数 $n$ 。所以 $v$ 的取值范围是 $[0, \min(n, x)]$ 。
对于每一个确定的 $v$ ，小i的任务数 $i$ 可以从 $0$ 取到他的上限 $y$ ，同时也不能超过剩余的任务数 $n-v$ 。所以 $i$ 的取值范围是 $[0, \min(n-v, y)]$ 。
当 $v$ 和 $i$ 的值确定后，分配给小o的任务数 $o$ 也就唯一确定了： $o = n - v - i$ 。
此时，我们已经通过循环的边界条件保证了 $v \le x$ , $i \le y$ 以及 $v+i+o=n$ 且 $o \ge 0$ 。唯一还需要检查的条件就是小o的任务数是否超过他的上限，即 $o \le z$ 。
如果 $o \le z$ 成立，说明我们找到了一个有效的分配方案，就将总方案数加一。
遍历完所有可能的 $v$ 和 $i$ 的组合后，累计的总方案数就是最终答案。

代码

cpp
java
python

#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    /**
     * 任务分配方案数计算
     * @param n int整型 待分配任务总数
     * @param x int整型 员工小v能处理的任务数上限
     * @param y int整型 员工小i能处理的任务数上限
     * @param z int整型 员工小o能处理的任务数上限
     * @return int整型
     */
    int assignJobs(int n, int x, int y, int z) {
        int count = 0;
        // 枚举小v的任务数v
        for (int v = 0; v <= min(n, x); ++v) {
            // 枚举小i的任务数i
            for (int i = 0; i <= min(n - v, y); ++i) {
                // 计算小o的任务数o
                int o = n - v - i;
                // 检查小o的任务数是否在其能力范围内
                if (o <= z) {
                    count++;
                }
            }
        }
        return count;
    }
};

import java.util.*;

public class Solution {
    /**
     * 任务分配方案数计算
     * @param n int整型 待分配任务总数
     * @param x int整型 员工小v能处理的任务数上限
     * @param y int整型 员工小i能处理的任务数上限
     * @param z int整型 员工小o能处理的任务数上限
     * @return int整型
     */
    public int assignJobs(int n, int x, int y, int z) {
        int count = 0;
        // 枚举小v的任务数v
        for (int v = 0; v <= Math.min(n, x); v++) {
            // 枚举小i的任务数i
            for (int i = 0; i <= Math.min(n - v, y); i++) {
                // 计算小o的任务数o
                int o = n - v - i;
                // 检查小o的任务数是否在其能力范围内
                if (o <= z) {
                    count++;
                }
            }
        }
        return count;
    }
}

class Solution:
    def assignJobs(self , n: int, x: int, y: int, z: int) -> int:
        count = 0
        # 枚举小v的任务数v
        for v in range(min(n, x) + 1):
            # 枚举小i的任务数i
            for i in range(min(n - v, y) + 1):
                # 计算小o的任务数o
                o = n - v - i
                # 检查小o的任务数是否在其能力范围内
                if o <= z:
                    count += 1
        return count

算法及复杂度

算法：暴力枚举
时间复杂度：两层循环的复杂度由 $x$ 和 $y$ 决定。外层循环最多执行 $x+1$ 次，内层循环最多执行 $y+1$ 次。因此，总的时间复杂度为 $O(x \cdot y)$ 。
空间复杂度：算法只使用了常数个额外变量，因此空间复杂度为 $O(1)$ 。