不浪费原料的汉堡制作方案(LeetCode日记)

LeetCode-1276-不浪费原料的汉堡制作方案

题目信息:

圣诞活动预热开始啦，汉堡店推出了全新的汉堡套餐。为了避免浪费原料，请你帮他们制定合适的制作计划。

给你两个整数 $tomatoSlices$ 和 $cheeseSlices$，分别表示番茄片和奶酪片的数目。不同汉堡的原料搭配如下：

• 巨无霸汉堡：4 片番茄和 1 片奶酪
• 小皇堡：2 片番茄和 1 片奶酪

请你以 $[tota{l}_{j}umbo,tota{l}_{s}mall]$（[巨无霸汉堡总数，小皇堡总数]）的格式返回恰当的制作方案，使得剩下的番茄片 $tomatoSlices$ 和奶酪片 $cheeseSlices$ 的数量都是 0。

如果无法使剩下的番茄片 $tomatoSlices$ 和奶酪片 $cheeseSlices$ 的数量为 0，就请返回 $[]$。

• 示例1：

输入：tomatoSlices = 16, cheeseSlices = 7
输出：[1,6]
解释：制作 1 个巨无霸汉堡和 6 个小皇堡需要 41 + 26 = 16 片番茄和 1 + 6 = 7 片奶酪。不会剩下原料。

• 示例2：

输入：tomatoSlices = 17, cheeseSlices = 4
输出：[ ]
解释：只制作小皇堡和巨无霸汉堡无法用光全部原料。

• 示例3：

输入：tomatoSlices = 4, cheeseSlices = 17
输出：[]
解释：制作 1 个巨无霸汉堡会剩下 16 片奶酪，制作 2 个小皇堡会剩下 15 片奶酪。

• 示例4：

输入：tomatoSlices = 0, cheeseSlices = 0
输出：[0,0]

• 示例5：

输入：tomatoSlices = 2, cheeseSlices = 1
输出：[0,1]

提示：

• $0<=tomatoSlices<=10^7$
• $0<=cheeseSlices<=10^7$

相关标签 ：数学

题解

今天的问题是一个典型的鸡兔同笼问题，还是相对简单的。

方法：数学

设巨无霸汉堡有 xxx 个，皇堡有 yyy 个，由于所有的材料都需要用完，因此我们可以得到二元一次方程组：

$$\{\begin{array}{l}4x+2y=\text{?tomatoSlices?}\\ x+y=\text{?cheeseSlices?}\end{array}$$

根据题意，$x,y\ge 0x,y\ge 0x,y\ge 0且x,y\in Nx,y\in \mathbb{N}x,y\in N$ ，解方程，得：
$$?\begin{array}{l}\text{?tomatoSlices?}=2k,k\in \mathbb{N}\\ \text{?tomatoSlices?}\ge 2\times \text{?cheeseSlices?}\\ 4\times \text{?cheeseSlices?}\ge \text{?tomatoSlices?}\end{array}$$

实现代码(Python)

class Solution:
    def numOfBurgers(self, tomatoSlices: int, cheeseSlices: int) -> List[int]:
        if tomatoSlices % 2 != 0 \
        or tomatoSlices < cheeseSlices * 2 \
        or cheeseSlices * 4 < tomatoSlices:
            return []
        return [tomatoSlices // 2 - cheeseSlices, \
        cheeseSlices * 2 - tomatoSlices // 2]

复杂度分析：

• 时间复杂度：$O(1)$ 。
• 空间复杂度：$O(1)$ 。

题记：

---

• 研究生在读，我会尽量保持LeetCode每日一题的思路和代码输出。希望大家多多支持。
• 水平有限，希望各位大佬能够批评指正。您的教诲是我进步的船帆。
• 希望各位跟我一样的小白能跟我一起参与到做题和讨论中来。共同进步是我所能期盼的最高愿想。
• 您的点赞和关注是我坚持分享的动力泉源，希望能将这件简单平凡的事一直做下去。感谢大家。

---