【儿须成名酒须醉】Python3+排序+贪心+数学证明+模拟

提交结果

• 执行用时： 164 ms , 在所有 Python3 提交中击败了 94.62% 的用户
• 内存消耗： 42.6 MB , 在所有 Python3 提交中击败了 58.06% 的用户
• 通过测试用例： 42 / 42

解题思路

1. 考虑两个任务的能量组合任务1为$[a_1,m_1]$与任务2为$[a_2,m_2]$
2. 则先做任务1再做任务2的最小初始能量为$s_{12}=max(m_1,m_2+a_1)$，反之则是$s_{21}=max(m_2,m_1+a_2)$
3. 不失一般地设$m_1-a_1>=m_2-a_2$，则有$m_1+a_2>=m_2+a_1$

• 当$m_1<=m_2$时，显然有$s_{12}=m_2+a_1$，而$s_{21}=max(m_2,m_1+a_2)$，由上可得$m_2+a_1<=m_1+a_2$，因此有$s_{12}<=s_{21}$
• 当$m_1>m_2$时，显然有$s_{12}=max(m_1,m_2+a_1)$，而$s_{21}=m_1+a_2$，由上可得$m_2+a_1<=m_1+a_2$，因此有$s_{12}<=s_{21}$

4. 由此使用归纳法可知，贪心地将任务$[a,m]$当中$m-a$较大即$a-m$较小的排在前面进行即可

性能优化

• 无

复杂度分析

• 设任务个数为$n$，则有
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(1)$

代码

###python3

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda x: x[0] - x[1])
        ans = 0
        cur = 0
        for a, m in tasks:
            if cur < m:
                ans += m - cur
                cur = m
            cur -= a
        return ans

逆向思维

从结果状态反推：$初始能量=总消耗能量+剩余能量$ 在剩余能量为$0$时的初始能量最优

• 执行用时： 180 ms , 在所有 Python3 提交中击败了 80.65% 的用户
• 内存消耗： 42.5 MB , 在所有 Python3 提交中击败了 81.72% 的用户
• 通过测试用例： 42 / 42

代码

###python3

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda x: x[1] - x[0])
        ans = 0
        for a, m in tasks:
            ans = ans + a if ans + a > m else m
        return ans