Leetcode.2591 将钱分给最多的儿童

题目链接

Leetcode.2591 将钱分给最多的儿童 rating : 1531

题目描述

给你一个整数 $money$ ，表示你总共有的钱数（单位为美元）和另一个整数 $children$ ，表示你要将钱分配给多少个儿童。

你需要按照如下规则分配：

• 所有的钱都必须被分配。
• 每个儿童至少获得 $1$ 美元。
• 没有人获得 $4$ 美元。

请你按照上述规则分配金钱，并返回 最多 有多少个儿童获得 恰好 $8$ 美元。如果没有任何分配方案，返回 $-1$ 。

示例 1：

输入：money = 20, children = 3
输出：1
解释：
最多获得 8 美元的儿童数为 1 。一种分配方案为：

• 给第一个儿童分配 8 美元。
• 给第二个儿童分配 9 美元。
• 给第三个儿童分配 3 美元。
  没有分配方案能让获得 8 美元的儿童数超过 1 。

示例 2：

输入：money = 16, children = 2
输出：2
解释：每个儿童都可以获得 8 美元。

提示：

• $1\le money\le 200$
• $2\le children\le 30$

解法：数学

要求每一个儿童都至少被分配 $1$ 美元，所以 $money\ge children$。

如果 $money<children$，说明不符合基本要求，直接返回 $-1$。

我们给每一个儿童先分配 $1$ 美元，即：

$$money=money-children$$

我们要凑成 $8$ 美元，只需要再给这些儿童每个分配 $7$ 美元即可，此时我们再计算出最多可以分配 $cnt$ 个 $7$ 美元：

$$cnt=min(money/7,children)$$

那么此时就有 $cnt$ 个儿童被分配了 $8$ 美元，我们还需要讨论。

分配了之后，剩余的钱 和 儿童数量：

$$\begin{gathered} money=money-cnt\times 7 \\ children=children-cnt \end{gathered}$$

• 如果此时 $children=0,money>0$，说明此时所有儿童都被分配了 $8$ 美元，此外还多出来了 $money$ 美元美元被分配，由于所有的钱都必须被分配，所以剩余美元只能被分配到一个儿童身上，拥有 $8$ 美元的儿童数量就要减一，即 $cnt=cnt-1$；

• 如果此时 $children=1,money=3$ ，说明此时除了最后一个儿童，其他儿童都被分配了 $8$ 美元。但是此时 $money$ 剩余了 $3$ 美元，分配到最后一个儿童身上就是 $4$ 美元，由于我们不能分配 $4$ 美元，所以只能将其分到其他儿童身上， 拥有 $8$ 美元的儿童数量就要减一，即 $cnt=cnt-1$；

• 其他情况都不用管；

时间复杂度： $O(1)$

C++代码：

class Solution {
public:
    int distMoney(int money, int c) {
        if(money < c) return -1;
        money -= c;

        int cnt = min(money / 7 , c);
        c -= cnt;
        money -= 7 * cnt;

        if((c == 0 && money > 0) || (c == 1 && money == 3)) cnt--;

        return cnt;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15