【2591. 将钱分给最多的儿童】

来源：力扣（LeetCode）

描述：

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

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

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

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

示例 1：

输入：money = 20, children = 3
输出：1
解释：
最多获得 8 美元的儿童数为 1 。一种分配方案为：
- 给第一个儿童分配 8 美元。
- 给第二个儿童分配 9 美元。
- 给第三个儿童分配 3 美元。
没有分配方案能让获得 8 美元的儿童数超过 1 。
1
2
3
4
5
6
7
8

示例 2：

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

提示：

• 1 <= money <= 200
• 2 <= children <= 30

方法：贪心

思路与算法

首先，若 money < children，则无解，返回 −1。

然后，给每个人先分配 111 美元，令 money 减去 children。

接着，给尽可能多的人分配 7 美元（加上前面分配的 1 美元就是 8 美元），这样最多分给 cnt = min⁡(⌊$\frac{money}{7}$ ⌋,children) 个人。

令 money 减去 7 × cnt，children 减去 cnt。此时还剩余 money 美元和 children 个人，进行分类讨论：

1. 若剩余 0 个人，并且 money > 0，那么将所有的美元分配给一个已经分到 8 美元的人，令 cnt 减去 1。
2. 若剩余 1 个人，并且 money = 3，为了避免分到 4 美元，并注意到题目输入中的 children >= 2，因此将这 3 美元拆成两部分，将其中的一部分分配给已经分到 8 美元的人，令 cnt 减去 1。
3. 对于其他情况，若 money > 0，可以将所有美元分配给一个人，cnt 不变。

代码：

class Solution {
public:
    int distMoney(int money, int children) {
        if (money < children) {
            return -1;
        }
        money -= children;
        int cnt = min(money / 7, children);
        money -= cnt * 7;
        children -= cnt;
        if ((children == 0 && money > 0) || (children == 1 && money == 3)) {
            cnt--;
        }
        return cnt;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间 8ms 击败 34.59%使用 C++ 的用户
内存 5.95MB 击败 7.30%使用 C++ 的用户
复杂度分析

• 时间复杂度： O(1)。
• 空间复杂度： O(1)。
  author：力扣官方题解