[每日一题] 1953.你可以工作的最大周数

2024 年 05 月 16 日

95 次浏览

1116字数

> https://leetcode.cn/problems/maximum-number-of-weeks-for-which-you-can-work/description/?envType=daily-question&envId=2024-05-06

偏数学的一道题。设阶段最多的任务为 $longest$ ，其余任务的阶段数总和为 $rest$ ，可以证明所有任务都能做完的充要条件是 $longest \leq rest + 1$ 。

该条件的必要性可以通过逆否命题证明，即当 $longest > rest + 1$ 时，无法完成所有任务。显然该结论成立，因为长度为 $longest$ 的任务有 $longest - 1$ 个间隔需要填充其它任务，可以通过反证法证明必要性。

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

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

因此只需要判断 $longest$ 和 $rest$ 之间的 关系就可以解出这道题：

```c++
class Solution {
public:
    long long numberOfWeeks(std::vector<int>& milestones) {
        long long most = *std::max_element(milestones.begin(), milestones.end());
        long long sum = std::accumulate(milestones.begin(), milestones.end(), 0LL);
        return sum >= 2 * most ? sum : 2 * (sum - most) + 1;
    }
};
```

- 时间复杂度：$O(n)$ ，其中 $n$ 为 `milestones` 数组的长度。
- 空间复杂度：$O(1)$ 。

最后修改：2024 年 05 月 16 日