题目描述
给你一个整数 money
,表示你总共有的钱数(单位为美元)和另一个整数 children
,表示你要将钱分配给多少个儿童。
你需要按照如下规则分配:
- 所有的钱都必须被分配。
- 每个儿童至少获得
1
美元。 - 没有人获得
4
美元。
请你按照上述规则分配金钱,并返回 最多 有多少个儿童获得 恰好 8
美元。如果没有任何分配方案,返回 -1
。
样例
输入:money = 20, children = 3
输出:1
解释:
最多获得 8 美元的儿童数为 1。一种分配方案为:
- 给第一个儿童分配 8 美元。
- 给第二个儿童分配 9 美元。
- 给第三个儿童分配 3 美元。
没有分配方案能让获得 8 美元的儿童数超过 1。
输入:money = 16, children = 2
输出:2
解释:每个儿童都可以获得 8 美元。
限制
1 <= money <= 200
2 <= children <= 30
算法
(分类讨论) $O(1)$
- 如果 $money < children$,则返回 $-1$。
- 如果 $money > 8 \cdot children$,则返回 $children - 1$,因为必然有一个儿童拿到超过 $8$ 美元。
- 令 $x := \lfloor \frac{money - children}{7} \rfloor$,$r := money - children - x * 7$。也就是说,当至少给每个儿童 $1$ 美元后,判断手里的钱最多够额外给多少个儿童 $7$ 美元。
- 如果 $x$ 等于 $children - 1$,且 $r = 3$,也就是分完额外的 $7$ 美元后,剩一个儿童,且还剩 $3$ 美元,则需要再减少一个拿到 $8$ 美元的儿童,以避免最后一个儿童拿到 $4$ 美元。
时间复杂度
- 三种情况讨论,时间复杂度为常数。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int distMoney(int money, int children) {
if (money < children)
return -1;
if (money > children * 8)
return children - 1;
int x = (money - children) / 7;
int r = (money - children) % 7;
if (x == children - 1 && r == 3)
return x - 1;
return x;
}
};