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

示例 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 <= 10^5
1 <= milestones[i] <= 10^9

class Solution { // 错误解 [5,7,5,7,9,7]
public:
    long long numberOfWeeks(vector<int>& milestones) {
        long long ans = 0;
        priority_queue<int> q(milestones.begin(), milestones.end());
        while(q.size() > 1)
        {
            int m1 = q.top();
            q.pop();
            int m2 = q.top();
            q.pop();
            ans = ans+m2+m2;
            if(m1-m2>0)
                q.push(m1-m2);
        }
        ans += !q.empty();
        return ans;
    }
};

class Solution {
public:
    long long numberOfWeeks(vector<int>& milestones) {
        long long sum = accumulate(milestones.begin(), milestones.end(), 0LL);
        int maxval = *max_element(milestones.begin(), milestones.end());
        if(maxval > sum-maxval) // 最多的大于剩余的，他自己肯定消耗不完
            return (sum-maxval)*2+1;
        return sum; // 否则，可以全部消耗完
    }
};