给你一个整数 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
方法一：贪心
思路与算法
首先，若 money} < \textit{children，则无解，返回 -1。
然后，给每个人先分配 1 美元，令 money 减去 children。
接着，给尽可能多的人分配 7 美元（加上前面分配的 1 美元就是 8 美元），这样最多分给 cnt} = \min(\lfloor \dfrac{\textit{money} }{7} \rfloor, \textit{children}) 个人。
令 money 减去 7 \times \textit{cnt，children 减去 cnt。此时还剩余 money 美元和 children 个人，进行分类讨论：
- 若剩余 0 个人，并且 money} > 0，那么将所有的美元分配给一个已经分到 8 美元的人，令 cnt 减去 1。
- 若剩余 1 个人，并且 money} = 3，为了避免分到 4 美元，并注意到题目输入中的 children} >= 2，因此将这 3 美元拆成两部分，将其中的一部分分配给已经分到 8 美元的人，令 cnt 减去 1。
- 对于其他情况，若 money} > 0，可以将所有美元分配给一个人，cnt 不变。
代码
[sol1-C++]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;
}
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;
}
};
|
[sol1-Java]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;
}
money -= children;
int cnt = Math.min(money / 7, children);
money -= cnt * 7;
children -= cnt;
if ((children == 0 && money > 0) || (children == 1 && money == 3)) {
cnt--;
}
return cnt;
}
}
|
[sol1-C#]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public class Solution {
public int DistMoney(int money, int children) {
if (money < children) {
return -1;
}
money -= children;
int cnt = Math.Min(money / 7, children);
money -= cnt * 7;
children -= cnt;
if ((children == 0 && money > 0) || (children == 1 && money == 3)) {
cnt--;
}
return cnt;
}
}
|
[sol1-C]1
2
3
4
5
6
7
8
9
10
11
12
13
| int distMoney(int money, int children) {
if (money < children) {
return -1;
}
money -= children;
int cnt = fmin(money / 7, children);
money -= cnt * 7;
children -= cnt;
if ((children == 0 && money > 0) || (children == 1 && money == 3)) {
cnt--;
}
return cnt;
}
|
[sol1-Python]1
2
3
4
5
6
7
8
9
10
11
| class Solution:
def distMoney(self, money: int, children: int) -> int:
if money < children:
return -1
money -= children
cnt = min(money // 7, children)
money -= cnt * 7
children -= cnt
if (children == 0 and money > 0) or (children == 1 and money == 3):
cnt -= 1
return cnt
|
[sol1-Go]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| func distMoney(money int, children int) int {
if money < children {
return -1
}
money -= children
cnt := min(money / 7, children)
money -= cnt * 7
children -= cnt
if (children == 0 && money > 0) || (children == 1 && money == 3) {
cnt -= 1
}
return cnt
}
func min(x int, y int) int {
if x > y {
return y
}
return x
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
12
13
| var distMoney = function(money, children) {
if (money < children) {
return -1;
}
money -= children
let cnt = Math.min(Math.floor(money / 7), children);
money -= cnt * 7;
children -= cnt;
if ((children == 0 && money > 0) || (children == 1 && money == 3)) {
cnt -= 1;
}
return cnt;
};
|
复杂度分析
