TURO OA 面试真题解析：App to Help Grandparents Divide Their Giving Budget｜贪心分配与“8/4”规则

Build an app to help grandparents divide their giving budget among their grandchildren. Write a program that calculates the number of lucky gifts (equal to 8) based on the budget and the number of grandchildren.

How it works

Many rules, mixing tradition and superstition, govern this gift.

• Gifts must not contain the amount 4, as this sounds like “death”.
• It is auspicious to give an amount of 8, as this sounds like “fortune”.
• It would be wrong to give nothing to any of the grandchildren.

So your algorithm should return the number of gifts equal to following these rules:

• Spend the entire budget, unless there is enough budget to give 8 to everyone.
• Do not give any 4; by tradition, the budget will never be 4.
• Do not give any 0, unless there is not enough money for all giftees.
• Give a maximum amount of 8 once the above rules are met.

Examples

• Classic budget: money = 11, giftees = 2. One lucky grandchild could get 8 and the other could get 3, so the function must return 1.
• Perfect budget: money = 32, giftees = 4. It is possible to give 8 to all the grandchildren, so we must return 4.
• Budget with a four: money = 12, giftees = 2. If the first grandchild gets 8 then the second would get 4, which is forbidden. Whatever the choice (7 and 5, or 6 and 6), nobody will get an amount of 8, so we must return 0.

这题本质上是一个带有“4 禁忌、8 吉利”规则的贪心分配问题：给定总预算和 grandchildren 数量，要把钱分给每个人且尽量让获得 8 元的孩子数量最多。关键在于判断是否能让所有人都至少拿到 8；如果预算足够直接返回人数。否则，由于不能出现 4，也不能有人拿 0，因此需要围绕 8 做合法拆分，并在不违反规则的前提下统计最多能有多少个 8。样例中 11 分给 2 人可以拆成 8 和 3，所以答案是 1；32 分给 4 人可以全部是 8，所以答案是 4；12 分给 2 人无论怎么分都无法产生 8，答案为 0。