力扣1953-你可以工作的最大周数（中等）

题目描述

• 给你 n 个项目，编号从 0 到 n - 1 。同时给你一个整数数组 milestones ，其中每个 milestones[i] 表示第 i 个项目中的阶段任务数量。

  你可以按下面两个规则参与项目中的工作：

  • 每周，你将会完成 某一个 项目中的 恰好一个 阶段任务。你每周都 必须 工作。
  • 在 连续的 两周中，你 不能 参与并完成同一个项目中的两个阶段任务。

  一旦所有项目中的全部阶段任务都完成，或者仅剩余一个阶段任务都会导致你违反上面的规则，那么你将 停止工作 。注意，由于这些条件的限制，你可能无法完成所有阶段任务。

  返回在不违反上面规则的情况下你 最多 能工作多少周。

方法一：贪心法

思路

考虑耗时最长的工作。假设我们需要 longest 周完成该工作，其余工作共计需要 rest 周完成。那么可以完成所有工作的充要条件是：longest ≤ rest + 1

证明

（必要性）必要性可以通过证明逆否命题，即「如果 longest>rest+1，那么无法完成所有的工作」，来证明。

我们可以利用反证法，如果可以完成所有工作，那么耗时最长的工作一定可以完成，这意味着至少需要有longest−1 周剩余工作可以被分配在间隔内，但剩余工作的工时 rest并不满足这一要求，因此充分性得证。

（充分性）充分性可以通过构造分配方案来证明。我们可以将分配工作时间的过程转化为在 [1,longest+rest] 闭区间内分配整数的过程，其中每个整数代表对应的一周时间。在分配整数的过程中，我们首先按照从小到大的顺序分配所有的奇数，然后按照从小到大的顺序分配所有的偶数。

我们将所有工作按照耗时从高到低来排序，按照前文的顺序分配对应的时间。此时由于 longest≤rest+1\textit{longest} \le \textit{rest} + 1longest≤rest+1，因此耗时最长的工作不会出现任意两周相邻这种违反规定的情况。类似地可以证明，其他工作由于耗时小于最长的工作，也不会出现相邻的情况。因此必要性得证。

算法

我们首先计算出耗时最长的工作所需周数 longest 与剩余工作所需周数 rest，并比较两者大小。根据比较的结果不同会有两种情况：

longest≤rest+1，此时根据 提示 111，所有工作都可以完成，我们返回所有工作的总耗时 longest+rest 作为答案。

longest>rest+1，此时我们无法完成耗时最长的工作。根据 提示 111 的证明过程，耗时最长的工作最多可以完成 rest+1周，因此最大的工作周数即为2×rest+1，我们返回该数作为答案。

最后，由于 rest 可能超过 32 位整数的范围，我们需要使用 64 位整数进行相应的计算与比较。

代码

class Question1953 {
    public long numberOfWeeks(int[] milestones) {
        int maxTime = Integer.MIN_VALUE;
        long sum = 0;
        for (int milestone : milestones) {
            maxTime = maxTime >= milestone ? maxTime : milestone;
            sum += milestone;
        }
        long rest = sum - maxTime;
        return (rest + 1 >= maxTime) ? sum : (2L * rest + 1);
    }
}