2591. 将钱分给最多的儿童

难度: 简单

来源: 每日一题 2023.09.22

---

给你一个整数 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

class Solution {
    public int distMoney(int money, int children) {

    }
}

分析与题解

---

• 贪心 + 情况分类 + 暴力

  这个问题, 想了半天也没有想到官方的题解方案. 所以就基于 对8整除的 除数 和 余数 进行分情况讨论了.

  int count = money/8;
  int subMoney = money%8;
  

  然后情况可以分为以下几种情况.

  • count数量 正好是 孩子数量 没有余数, count就是结果

  • count数量 正好是 孩子数量, 有余数, 有一个孩子要多拿余数 children-1 就是结果

    if (count == children) {
        if (subMoney > 0) {
            result = children - 1;
        } else {
            result = children;
        }
    }
    

  • count数量 比 孩子数量多, 有一个孩子要多拿剩余的钱 children-1 就是结果

    if (count > children) {
        result = children - 1;
    }
    

  • count数量 比 孩子数量 少, 从0个拿到8元的孩子 把钱拿出来 进行递归计算, 直到所有孩子都能拿到钱, 只有这种情况不满足才会有 -1 的出现

  • 没人获得4元, 只有一种case, 那就是剩余最后一个人拿4元, 两个人分多少钱都能规避这种情况.

    int noMoneyChildren = children - count;
    int outMoneyChildren = 0;
    while( ((noMoneyChildren > (subMoney + outMoneyChildren * 8) ) && outMoneyChildren <= count) ||
        (noMoneyChildren == 1 && subMoney + outMoneyChildren * 8 == 4)){
            // 再拿出一个孩子的8元钱
            outMoneyChildren++;
            // 没钱的孩子也要增加1
            noMoneyChildren++;
    }
    if (count - outMoneyChildren >= 0) {
        result = count - outMoneyChildren;
    }
    

  整体逻辑代码如下所示.

  class Solution {
      public int distMoney(int money, int children) {
          int result = -1;
          int count = money/8;
          int subMoney = money%8;
          if (count == children) {
              if (subMoney > 0) {
                  result = children - 1;
              } else {
                  result = children;
              }
          } else if (count > children) {
              result = children - 1;
          } else {
              int noMoneyChildren = children - count;
              int outMoneyChildren = 0;
              while( ((noMoneyChildren > (subMoney + outMoneyChildren * 8) ) && outMoneyChildren <= count) ||
              (noMoneyChildren == 1 && subMoney + outMoneyChildren * 8 == 4)){
                  // 再拿出一个孩子的8元钱
                  outMoneyChildren++;
                  // 没钱的孩子也要增加1
                  noMoneyChildren++;
              }
              if (count - outMoneyChildren >= 0) {
                  result = count - outMoneyChildren;
              }
          }
          return result;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n), while循环, 最多循环的次数是孩子的个数.
  • 空间复杂度: O(1), 常量级别的空间复杂度.

  结果如下所示.