2591. 将钱分给最多的儿童
来源第 100 场双周赛 Q1难度简单分数1530
题目描述
给你一个整数 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
解法
方法一:分类讨论
思考
每人至少 \(1\) 美元,得到 \(8\) 美元的人数尽量多,且不能有人恰好得到 \(4\) 美元。钱不够每人 \(1\) 美元则无解。
总额超过 \(8\times \textit{children}\) 时必须有人多于 \(8\),最多只能让 \(\textit{children}-1\) 人拿满 \(8\)。总额恰为 \(8n-4\) 时,若已有 \(n-1\) 人拿 \(8\),剩下的人会拿到 \(4\),故再少一人。其余情形每人先拿 \(1\),剩余每 \(7\) 美元可多造一个 \(8\),即 \(\lfloor(\textit{money}-\textit{children})/7\rfloor\)。
如果 \(\textit{money} \lt \textit{children}\),那么一定存在儿童没有分到钱,返回 \(-1\)。
如果 \(\textit{money} \gt 8 \times \textit{children}\),那么有 \(\textit{children}-1\) 个儿童获得了 \(8\) 美元,剩下的一个儿童获得了 \(\textit{money} - 8 \times (\textit{children}-1)\) 美元,返回 \(\textit{children}-1\)。
如果 \(\textit{money} = 8 \times \textit{children} - 4\),那么有 \(\textit{children}-2\) 个儿童获得了 \(8\) 美元,剩下的两个儿童分摊剩下的 \(12\) 美元(只要不是 \(4\), \(8\) 美元就行),返回 \(\textit{children}-2\)。
如果,我们假设有 \(x\) 个儿童获得了 \(8\) 美元,那么剩下的钱为 \(\textit{money}- 8 \times x\),只要保证大于等于剩下的儿童数 \(\textit{children}-x\),就可以满足题意。因此,我们只需要求出 \(x\) 的最大值,即为答案。
时间复杂度 \(O(1)\),空间复杂度 \(O(1)\)。
1 2 3 4 5 6 7 8 9 10 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 | |
1 2 3 4 5 6 7 8 9 10 11 12 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | |