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

Every day a Leetcode

题目来源：1953. 你可以工作的最大周数

类似题目：621. 任务调度器

解法1：贪心

本质上来说，我们需要构造一个尽量长的，相邻元素不同的序列，且元素 x 的出现次数不能超过 milestones[x]。

设 milestones 的元素和为 s，这是序列长度的上界。设 mx=max⁡(milestones)，我们可以把该任务的阶段任务每次间隔 1 位排列在序列中，其他的任务则安排在空位上，这样的构造方法能保证序列最长。

如果 mx 特别大，大到它比其它元素的个数之和加 1 还要大，即 mx > s - mx + 1，那么说明 mx 这个任务不能全部完成，它只能安排 s - mx + 1 个阶段任务，此时能完成的阶段任务数为 (s - mx) + (s - mx + 1) = 2 * (s - mx) + 1；否则，所有任务都能全部完成，能完成的阶段任务数为 s。

代码：

/*
 * @lc app=leetcode.cn id=1953 lang=cpp
 *
 * [1953] 你可以工作的最大周数
 */

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

结果：

复杂度分析：

时间复杂度：O(n)，其中 n 是数组 milestones 的长度。

空间复杂度：O(1)。