2591.将钱分给最多的儿童
【LetMeFly】2591.将钱分给最多的儿童
力扣题目链接:https://leetcode.cn/problems/distribute-money-to-maximum-children/
给你一个整数 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比儿童数还少,返回-1
- 如果money特别多(每人分8美元还有剩余),就$children - 1$个儿童每人分8美元,剩下的全给另一个儿童
- 否则,每个儿童先分1美元,接着尽可能地给每个儿童分7美元,则8美元儿童的个数为$\lfloor\frac{money - children}{7}\rfloor$,将剩余钱(≤7)分给其他儿童:
- 如果恰好剩余3元且恰好剩余1个儿童,因为不能给他4美元,所以要从一个8美元儿童中转给他1美元(此时money = children * 8 - 4,8美元儿童数量为children - 2)
- 否则,一定存在一种方案使得非8美元儿童的钱都不是4。
注意儿童数是≥2的,所以不存在“仅有1个儿童且恰好有4美元的情况”。
- 时间复杂度$O(1)$
- 空间复杂度$O(1)$
AC代码
C++
1 |
|
Python
1 |
|
同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/133167460
2591.将钱分给最多的儿童
https://blog.letmefly.xyz/2023/09/22/LeetCode 2591.将钱分给最多的儿童/