1953. 你可以工作的最大周数（Rating 1804）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

1953. 你可以工作的最大周数

Rating 1804

思路

看到第二个示例[5, 2, 1]，想到

如果数组中一个值非常大，比其余所有值的和加起来都大，那么我们就可以以这个大数为基准，用剩余的数把这个数分开。

例如[5, 2, 1]分别代表5个A工作，2个B工作，1个C工作，那么考虑用BC插空A

A B A B A C A

这样，如果【最大的数】大于等于【剩余数的和 + 1】，那么答案就是【2 * 剩余数的和 + 1】

那么，不是这样的情况怎么办？

这里我是直接猜的答案，一种直觉，即猜测这种情况下【一定可以全部完成】，答案是数组所有数字求和。

但是没有想到证明思路。

后来参考 灵神的题解，第二种情况可以以这样一种构造思路：

把 milestones 从大到小排序，按照先填偶数下标，再填奇数下标的方式进行。

假设有重复，那么一定是我们先填完了偶数下标，再填奇数下标时重复了。

由于在第二种情况，【最大的数】一定小于【剩余数的和 + 1】，那么按照上面的方式构造一定不会出现重复的现象，否则就有一个非常大的数存在了。

因此，一定可以全部完成。

代码

class Solution:
    def numberOfWeeks(self, milestones: List[int]) -> int:
        m = max(milestones)
        s = sum(milestones)
        r = s - m
        if m >= r + 1:
            return 2 * r + 1
        return s