[LeetCode] 2591. 将钱分给最多的儿童

给你一个整数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 - children 美元，然后试着用剩下的钱去分给儿童 7 美元，看能分多少人。要注意的是三个情况：其一是 money - children < 0说明根本做不到人人有钱分的要求,返回 -1。其二是给每个儿童都补了 7 美元发现钱有剩，即 money > 8*children 的情况， 这时候有一个人必然会持有剩余的 money - 8 * children 美元，所以会导致恰好获得 8 美元人数减 1。最后一种情况是分下来有个儿童持有 4 美元， 所以必须拆一个 8 美元的分配给这个 4 美元的儿童来满足“没有人获得 4 美元”的规则。

AC代码:

class Solution {
public:
    int distMoney(int money, int children) {
        if (money < children) {
            return -1;
        }
        int count = (money - children) / 7;
        if (count > children) {
            count = children;
        }
        int remaining_money = money - count * 8;
        int remaining_children = children - count;

        if (remaining_children == 0 && remaining_money > 0) {
            count -= 1;
        }
        else if (remaining_children == 1 && remaining_money == 4) {
            count -= 1;
        }
        
        return count < 0 ? -1 : count;
    }
};Code language: C++ (cpp)