Easy

题目描述

给你一个整数 money ，表示你拥有的钱数（以美元为单位），以及另一个整数 children ，表示你必须将钱分给孩子的数目。

你需要按照如下规则分配：

  • 所有的钱都必须被分配。
  • 每个人必须至少得到 1 美元。
  • 没有人得到 4 美元。

如果你按照上述规则分配金钱，返回 最多 有多少个孩子可以得到 恰好 8 美元。如果无法按规则分配金钱，返回 -1 。

示例 1：

输入：money = 20, children = 3
输出：1
解释：
最多有 1 个孩子得到 8 美元。分配方案之一为：
- 给第一个孩子 8 美元。
- 给第二个孩子 9 美元。
- 给第三个孩子 3 美元。
可以证明分配方案中让得到 8 美元的孩子数目大于 1 是不可能的。

示例 2：

输入：money = 16, children = 2
输出：2
解释：每个孩子都可以得到 8 美元。

提示：

  • 1 <= money <= 200
  • 2 <= children <= 30

解题思路

解题思路

这是一个贪心问题，我们需要在满足约束条件的前提下，最大化得到 8 美元的孩子数量。

分析约束条件

  1. 所有钱必须分完
  2. 每个孩子至少得到 1 美元
  3. 没有孩子得到 4 美元

贪心策略

为了最大化得到 8 美元的孩子数量，我们可以尽可能多地给孩子 8 美元，剩下的孩子给最少的钱（但不能是 4 美元）。

解法步骤

  1. 首先检查基础可行性：money < children 时无法满足每人至少 1 美元的要求
  2. 从最多可能的 8 美元孩子数开始尝试（不超过 min(money/8, children)）
  3. 对于每个可能的 8 美元孩子数 k，检查是否能合理分配剩余的钱给其他孩子
  4. 剩余的钱要分给 children - k 个孩子，每人至少 1 美元且不能是 4 美元

特殊情况处理

  • 如果只剩一个孩子且剩余钱数为 4，这是不允许的
  • 如果剩余钱数不足以给每个剩余孩子至少 1 美元，也是不可行的

通过从大到小尝试 k 值，第一个满足条件的就是答案。

代码实现

class Solution {
public:
    int distMoney(int money, int children) {
        // 基础检查：如果钱不够每人分1美元
        if (money < children) return -1;
        
        // 从最大可能的8美元孩子数开始尝试
        int maxEight = min(money / 8, children);
        
        for (int k = maxEight; k >= 0; k--) {
            int remaining = money - k * 8;
            int remainingChildren = children - k;
            
            // 如果没有剩余孩子，剩余钱数必须为0
            if (remainingChildren == 0) {
                if (remaining == 0) return k;
                continue;
            }
            
            // 剩余钱数必须足够给每个剩余孩子至少1美元
            if (remaining < remainingChildren) continue;
            
            // 特殊情况：如果只剩一个孩子且剩余钱为4美元，不允许
            if (remainingChildren == 1 && remaining == 4) continue;
            
            return k;
        }
        
        return -1;
    }
};

class Solution:
    def distMoney(self, money: int, children: int) -> int:
        # 基础检查：如果钱不够每人分1美元
        if money < children:
            return -1
        
        # 从最大可能的8美元孩子数开始尝试
        max_eight = min(money // 8, children)
        
        for k in range(max_eight, -1, -1):
            remaining = money - k * 8
            remaining_children = children - k
            
            # 如果没有剩余孩子，剩余钱数必须为0
            if remaining_children == 0:
                if remaining == 0:
                    return k
                continue
            
            # 剩余钱数必须足够给每个剩余孩子至少1美元
            if remaining < remaining_children:
                continue
            
            # 特殊情况：如果只剩一个孩子且剩余钱为4美元，不允许
            if remaining_children == 1 and remaining == 4:
                continue
            
            return k
        
        return -1

public class Solution {
    public int DistMoney(int money, int children) {
        // 基础检查：如果钱不够每人分1美元
        if (money < children) return -1;
        
        // 从最大可能的8美元孩子数开始尝试
        int maxEight = Math.Min(money / 8, children);
        
        for (int k = maxEight; k >= 0; k--) {
            int remaining = money - k * 8;
            int remainingChildren = children - k;
            
            // 如果没有剩余孩子，剩余钱数必须为0
            if (remainingChildren == 0) {
                if (remaining == 0) return k;
                continue;
            }
            
            // 剩余钱数必须足够给每个剩余孩子至少1美元
            if (remaining < remainingChildren) continue;
            
            // 特殊情况：如果只剩一个孩子且剩余钱为4美元，不允许
            if (remainingChildren == 1 && remaining == 4) continue;
            
            return k;
        }
        
        return -1;
    }
}

var distMoney = function(money, children) {
    if (money < children) return -1;
    
    money -= children;
    
    let eightDollarChildren = Math.min(Math.floor(money / 7), children);
    
    let remainingMoney = money - eightDollarChildren * 7;
    let remainingChildren = children - eightDollarChildren;
    
    if (remainingChildren == 1 && remainingMoney == 3) {
        eightDollarChildren--;
    }
    
    if (remainingChildren == 0 && remainingMoney > 0) {
        eightDollarChildren--;
    }
    
    return eightDollarChildren;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(min(money/8, children))
空间复杂度O(1)

说明：

  • 时间复杂度：最多需要尝试 min(money/8, children) 次，由于约束条件 money ≤ 200，children ≤ 30，所以实际复杂度很小
  • 空间复杂度：只使用常数额外空间

相关题目