跳转至

2591. 将钱分给最多的儿童

题目描述

给你一个整数 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 <= money <= 200
  • 2 <= children <= 30

解法

方法一：分类讨论

如果 \(money \lt children\)，那么一定存在儿童没有分到钱，返回 \(-1\)。

如果 \(money \gt 8 \times children\)，那么有 \(children-1\) 个儿童获得了 \(8\) 美元，剩下的一个儿童获得了 \(money - 8 \times (children-1)\) 美元，返回 \(children-1\)。

如果 \(money = 8 \times children - 4\)，那么有 \(children-2\) 个儿童获得了 \(8\) 美元，剩下的两个儿童分摊剩下的 \(12\) 美元（只要不是 \(4\), \(8\) 美元就行），返回 \(children-2\)。

如果，我们假设有 \(x\) 个儿童获得了 \(8\) 美元，那么剩下的钱为 \(money- 8 \times x\)，只要保证大于等于剩下的儿童数 \(children-x\)，就可以满足题意。因此，我们只需要求出 \(x\) 的最大值，即为答案。

时间复杂度 \(O(1)\)，空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def distMoney(self, money: int, children: int) -> int:
        if money < children:
            return -1
        if money > 8 * children:
            return children - 1
        if money == 8 * children - 4:
            return children - 2
        # money-8x >= children-x, x <= (money-children)/7
        return (money - children) // 7

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func distMoney(money int, children int) int {
    if money < children {
        return -1
    }
    if money > 8*children {
        return children - 1
    }
    if money == 8*children-4 {
        return children - 2
    }
    // money-8x >= children-x, x <= (money-children)/7
    return (money - children) / 7
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function distMoney(money: number, children: number): number {
    if (money < children) {
        return -1;
    }
    if (money > 8 * children) {
        return children - 1;
    }
    if (money === 8 * children - 4) {
        return children - 2;
    }
    return Math.floor((money - children) / 7);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
impl Solution {
    pub fn dist_money(money: i32, children: i32) -> i32 {
        if money < children {
            return -1;
        }

        if money > children * 8 {
            return children - 1;
        }

        if money == children * 8 - 4 {
            return children - 2;
        }

        (money - children) / 7
    }
}

评论