员工分组

[题目链接](https://www.nowcoder.com/practice/bbfaec07fc7c4763bed03fc9c0e23283)

思路

本题要求将新老员工分成最少的组，需要遵守三条规则：

每组最多 3 人；
每组最多 1 个老员工；
如果组里有老员工，则该组最多 2 人。

贪心策略

统计老员工数量 $ones$ 和新员工数量 $zeros$ 。

老员工必须独占一组（因为每组最多 1 个老员工），但每个老员工的组里还能带 1 个新员工（组上限为 2 人）。因此优先把新员工塞进老员工的组里，能消耗掉 $\min(ones, zeros)$ 个新员工。

剩余的新员工每 3 人一组，即需要 $\lceil \text{剩余新员工} / 3 \rceil$ 组。

最终答案为：

$ $ones + \left\lceil \frac{\max(0,\; zeros - ones)}{3} \right\rceil$ $

样例验证

[1,0,0,0,1]： $ones=2, zeros=3$ 。2 个老员工各带 1 个新员工，剩 1 个新员工单独一组。 $2 + \lceil 1/3 \rceil = 3$ 。
[1,1]： $ones=2, zeros=0$ 。2 个老员工各自一组。 $2 + 0 = 2$ 。

代码

C++
Java
Python3
JavaScript

class Solution {
public:
    int staffGroup(vector<int>& staff) {
        int ones = 0, zeros = 0;
        for (int x : staff) {
            if (x == 1) ones++;
            else zeros++;
        }
        int paired = min(ones, zeros);
        zeros -= paired;
        return ones + (zeros + 2) / 3;
    }
};

import java.util.*;

public class Solution {
    public int staffGroup(int[] staff) {
        int ones = 0, zeros = 0;
        for (int x : staff) {
            if (x == 1) ones++;
            else zeros++;
        }
        int paired = Math.min(ones, zeros);
        zeros -= paired;
        return ones + (zeros + 2) / 3;
    }
}

class Solution:
    def staffGroup(self, staff):
        ones = sum(staff)
        zeros = len(staff) - ones
        paired = min(ones, zeros)
        zeros -= paired
        return ones + (zeros + 2) // 3

function staffGroup(staff) {
    let ones = 0, zeros = 0;
    for (let x of staff) {
        if (x === 1) ones++;
        else zeros++;
    }
    let paired = Math.min(ones, zeros);
    zeros -= paired;
    return ones + Math.ceil(zeros / 3);
}

复杂度分析

时间复杂度： $O(n)$ ，其中 $n$ 是数组长度，遍历一次统计即可。
空间复杂度： $O(1)$ ，只使用常数个变量。