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

【LetMeFly】1953.你可以工作的最大周数：贪心（两个变量一次遍历秒了）

力扣题目链接：https://leetcode.cn/problems/maximum-number-of-weeks-for-which-you-can-work/

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

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

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

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

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

 

示例 1：

输入：milestones = [1,2,3]
输出：6
解释：一种可能的情形是：
​​​​- 第 1 周，你参与并完成项目 0 中的一个阶段任务。
- 第 2 周，你参与并完成项目 2 中的一个阶段任务。
- 第 3 周，你参与并完成项目 1 中的一个阶段任务。
- 第 4 周，你参与并完成项目 2 中的一个阶段任务。
- 第 5 周，你参与并完成项目 1 中的一个阶段任务。
- 第 6 周，你参与并完成项目 2 中的一个阶段任务。
总周数是 6 。

示例 2：

输入：milestones = [5,2,1]
输出：7
解释：一种可能的情形是：
- 第 1 周，你参与并完成项目 0 中的一个阶段任务。
- 第 2 周，你参与并完成项目 1 中的一个阶段任务。
- 第 3 周，你参与并完成项目 0 中的一个阶段任务。
- 第 4 周，你参与并完成项目 1 中的一个阶段任务。
- 第 5 周，你参与并完成项目 0 中的一个阶段任务。
- 第 6 周，你参与并完成项目 2 中的一个阶段任务。
- 第 7 周，你参与并完成项目 0 中的一个阶段任务。
总周数是 7 。
注意，你不能在第 8 周参与完成项目 0 中的最后一个阶段任务，因为这会违反规则。
因此，项目 0 中会有一个阶段任务维持未完成状态。

 

提示：

• n == milestones.length
• 1 <= n <= 105
• 1 <= milestones[i] <= 109

解题方法：贪心——两个变量+一次遍历

相邻两周工作内容不能相同，怎么安排才能工作最久？当然是小杂活穿插在最多的工作之间。小杂活是指“工作次数较少的任务”，最多的工作是指在所有工作当中次数最多的那个工作。

那么不就两种情况么？

1. “最多的工作”特别特别多（假设为A），那么只能“A、x、A、y、A、…、A”，最多工作$2\times A+1$周
2. “最多的工作”也不是很多（$A\times 2\leq 总工作量$），那么能在相邻工作不同的前提下安排完所有的工作

   怎么安排？假设任务为$A\times3+B\times4+C\times3+D$，则里面任务最多的是$B$。

   将B一个间隔一个地放置，直至序列末尾（B肯定不够用，没关系，那就使用另外任意一个或多个任务“接力”，直到放到末尾为止）

   初始为：$_\ _\ _\ _\ _\ _\ _\ _\ _\ _\ _\ $

   间隔放，用完所有的B用A：$B\ _\ B\ _\ B\ _\ B\ _\ A\ _\ A\ $

   若A还有剩余，则在剩下的空位中从前往后依次放置：$B\ A\ B\ _\ B\ _\ B\ _\ A\ _\ A\ $（这里因为A的数量很少，所以前面和后面的A一定不会相遇）

   剩下所有没被安排的任务，随意放喽，一定不会相邻了：$B\ A\ B\ C\ B\ C\ B\ C\ A\ D\ A\ $

因此只需要统计一下总共多少工时、最大工时是多少即可。

• 时间复杂度$O(n)$
• 空间复杂度$O(1)$

AC代码

C++

typedef long long ll;

class Solution {
public:
    ll numberOfWeeks(vector<int>& milestones) {
        ll cnt = 0, M = 0;
        for (int t : milestones) {
            cnt += t;
            M = max(M, (ll)t);
        }
        return M * 2 <= cnt ? cnt : (cnt - M) * 2 + 1;
    }
};

Python

# from typing import List

class Solution:
    def numberOfWeeks(self, milestones: List[int]) -> int:
        cnt, M  =0, 0
        for t in milestones:
            cnt += t
            M = max(M, t)
        return cnt if M * 2 <= cnt else (cnt - M) * 2 + 1

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/138974368