2022-02-05 每日打卡：Leetcode第71场双周赛

写在前面

“这些事儿在熟练之后，也许就像喝口水一样平淡，但却能给初学者带来巨大的快乐，我一直觉得，能否始终保持如初学者般的热情、专注，决定了在做某件事时能走多远，能做多好。” 该系列文章由python编写，所刷题目共三个来源：之前没做出来的 ；Leetcode中等，困难难度题目； 周赛题目；某个专题的经典题目，所有代码已AC。每日1-3道，随缘剖析，希望风雨无阻，作为勉励自己坚持刷题的记录。

T1~T3

• T1 拆分数位后四位数字的最小和：对于位数问题，可以使用字符串进行快速的划分和连接，字符串之间的相加减对应的就是每个位数之间的相加减。
• T2 根据给定数字划分数组：partition操作是否保持有序取决于采用双指针or单指针。
• T3 设置时间的最少代价：凡是给定数据范围，譬如此题中微波炉的时间设置为0~99，一定要在提交前测试一下边界，比如100的情况。

5987. 删除元素后和的最小差值

将 nums 拆分成两部分，划分位置区间为【n~2*n】，无论何种划分，最后取【左半部分的最小和（前缀最小和）】减去【右半部分的最大和（后缀最大和）】即为两部分和的最小差值。
枚举拆分位置（保证左右两部分至少有 n 个元素），所有差值的最小值就是答案。很多题并不是一下子就能出答案的，要接受适当的枚举。

from heapq import *

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        n = len(nums) // 3
        
        left = [0 for _ in range(3 * n + 1)]        # 划分到第i个时，i左侧最小的n个数的和
        right = [0 for _ in range(3 * n + 1)]       # 划分到第i个时，i右侧最大的n个数的和
        
        # 每次要删除那个最大的数
        # 在0~2n的区域中保留最小的n个
        l_max = []                          
        for i in range(2 * n):
            left[i + 1] = left[i] + nums[i]
            heapq.heappush(l_max, -1 * nums[i])
            if n <= i:
                left[i + 1] -= -1 * l_max[0]
                heapq.heappop(l_max)

        # 每次要删除那个最小的数
        # 在n~3n的区域中保留最大的n个
        r_min = []   
        for i in range(3 * n - 1, n - 1, -1):
            right[i] = right[i + 1] + nums[i]
            heapq.heappush(r_min, nums[i])
            if i < 2 * n:
                right[i] -= r_min[0]
                heapq.heappop(r_min)
        
        # 有效的划分区间
        left, right = left[n:2*n+1], right[n:2*n+1]
        res = min(l-r for l,r in zip(left,right))
        return res