🔗 🟡 1953. Maximum Number of Weeks for Which You Can Work 1804

tags: `Weekly Contest 252` `貪心(Greedy)` `數學(Math)`

你說的對，但我只想直接 return 0 。

題意

有 $n$ 個專案，編號從 $0$ 到 $n - 1$ 。給定一個整數陣列 $milestones$ ，其中每個 $milestones[i]$ 表示第 $i$ 個專案的階段任務數量。

必須按照以下兩個規則來完成專案中的任務：

每週都只能完成 某一個 專案中的 恰好一個 階段任務，且每週都必須工作。
在 連續的 兩週中，不能參與並完成同一個專案中的兩個階段任務。

返回在遵守上述規則的情況下，最多能工作多少週。

思路：貪心(Greedy) + 數學(Math)

首先先來想一下什麼情況下會無法完成所有專案。由於連續兩周必須要完成不同的專案，因此若有一個專案特別大，則就算交錯該專案與所有其他專案，也會導致完成其他專案後，剩下該專案未完成。

舉例來說，若專案 $a$ 有 $5$ 個任務、專案 $b$ 有 $2$ 個任務、專案 $c$ 有 $1$ 個任務，則無法完成所有任務，一種完成最多任務的方法為 $ababaca$ ，即將其餘任務插到最大任務數量的任務之間。

具體而言，令 $mx$ 為 $milestones$ 中的最大值， $s$ 為 $milestones$ 的總和，則：

若 $mx \leq s - mx + 1$ ，則可以完成所有專案，返回 $s$ 。
若 $mx > s - mx + 1$ ，則無法完成所有專案，返回 $2 \times (s - mx) + 1$ 。

複雜度分析

時間複雜度： $O(n)$
空間複雜度： $O(1)$

class Solution:
    def numberOfWeeks(self, milestones: List[int]) -> int:
        s = sum(milestones)
        mx = max(milestones)
        if mx > s - mx + 1: # 不能完成所有專案
            return 2*(s - mx) + 1
        else: # 可以完成所有專案
            return s

using LL = long long;
class Solution {
public:
    long long numberOfWeeks(vector<int>& milestones) {
        int mx = *max_element(milestones.begin(), milestones.end());
        LL s = accumulate(milestones.begin(), milestones.end(), 0LL);
        return (mx > s - mx + 1) ? (s - mx) << 1 | 1 : s;
    }
};