LeetCode 题解工作台
将钱分给最多的儿童
给你一个整数 money ，表示你总共有的钱数（单位为美元）和另一个整数 children ，表示你要将钱分配给多少个儿童。 你需要按照如下规则分配： 所有的钱都必须被分配。 每个儿童至少获得 1 美元。 没有人获得 4 美元。 请你按照上述规则分配金钱，并返回 最多 有多少个儿童获得 恰好 8 美…
2
题型
6
代码语言
3
相关题
当前训练重点
简单 · 贪心·invariant
答案摘要
如果 $money \lt children$，那么一定存在儿童没有分到钱，返回 。 如果 $money \gt 8 \times children$，那么有 个儿童获得了 美元，剩下的一个儿童获得了 $money - 8 \times (children-1)$ 美元，返回 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个整数 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 <= 2002 <= children <= 30
解题思路
方法一：分类讨论
如果 ，那么一定存在儿童没有分到钱，返回 。
如果 ，那么有 个儿童获得了 美元，剩下的一个儿童获得了 美元，返回 。
如果 ，那么有 个儿童获得了 美元，剩下的两个儿童分摊剩下的 美元（只要不是 , 美元就行），返回 。
如果，我们假设有 个儿童获得了 美元，那么剩下的钱为 ，只要保证大于等于剩下的儿童数 ，就可以满足题意。因此，我们只需要求出 的最大值，即为答案。
时间复杂度 ，空间复杂度 。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(1) because the maximum number of children is limited to 30, making simple arithmetic sufficient. Space complexity is O(1) as no extra structures are required beyond variable storage. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
You may be asked to explain why a simple greedy approach works for maximizing 8-dollar allocations.
- question_mark
Expect clarifying questions on validating the remaining money after initial assignments.
- question_mark
Interviewers might test edge cases like distributing all money evenly or having a remainder less than the number of remaining children.
常见陷阱
外企场景- error
Assuming you can always assign 8 dollars to floor(money/8) children without checking leftover constraints.
- error
Ignoring the rule that each child must get at least 1 dollar in validation steps.
- error
Failing to decrement the 8-dollar assignments when leftover money is insufficient, leading to incorrect -1 results.
进阶变体
外企场景- arrow_right_alt
Maximize children receiving a fixed amount other than 8 dollars, requiring similar greedy validation.
- arrow_right_alt
Distribute money with additional constraints such as maximum cap per child, testing more complex invariants.
- arrow_right_alt
Calculate minimum money required to guarantee at least k children receive 8 dollars.