首页 > 试题广场 >

员工分组

[编程题]员工分组

热度指数：145 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小美要将N名员工分成若干组，且每组至少要有一名员工。每个组都会产生一个单位的收益，且对于第i名员工，如果其所在的组包含至少A[i]名员工（包括第i名员工自身），则该员工会额外贡献一个单位的收益。现在，小美请小团将N名员工分组，使得总收益最大。

输入描述:

第一行输入一个整数T（1<=T<=10），表示数据组数。
每组数据占两行，第一行输入一个整数N（1<=N<=10^5）；
第二行输入N个由空格隔开的整数，表示A[1]到A[N]（1<=A[i]<=N）。

输出描述:

每组数据输出占一行，输出一个整数，表示总收益的最大值。

示例1

输入

4
3
2 3 3
4
2 2 2 2
5
3 2 5 1 4
6
2 3 4 1 3 2

输出

说明

对于第一组数据，将3名员工都分在一组；

对于第二组数据，将4名员工分成两组，每组2名；

对于第三组数据，将5名员工都分在一组；

对于第四组数据，将第4名员工分成一组，其他员工都分在另一组。

算法知识视频讲解

pein531

由于员工i所在的组至少要有A[i]人才能获得额外的一个收益，而不管A[i]是多少，达到这个人数后额外收益也只会是一个单位，因此为了获得额外的那个收益，应该尽可能先满足A[i]小的，这样获得额外收益的门槛更低。

先对A进行升序排列，然后利用动态规划求解，因为每人自成一组的情况下可以获得n个收益，因此初始化收益为n，dp[0] = n，用dp[i+1]表示0~i号员工分配到一组时的收益。易知i+1为第一组员工的人数，当i+1>=A[i]时，相较于0~i-A[i]号员工分在一组，会产生一个额外的收益，因此得到状态转移方程：

dp[i + 1] = dp[i + 1 - A[i]] + 1 (i + 1 >= A[i])

dp数组中的最大值就是所有方案中的最大收益。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        while(T-- > 0){
            int n = Integer.parseInt(br.readLine().trim());
            String[] strA = br.readLine().trim().split(" ");
            int[] A = new int[n];
            for(int i = 0; i < n; i++) A[i] = Integer.parseInt(strA[i]);
            // 对产生额外收益的“门槛”进行排序，先满足门槛低的员工
            Arrays.sort(A);
            int[] dp = new int[n + 1];
            // 初始化，每人一组至少有n的收益
            dp[0] = n;
            int maxIncome = dp[0];
            for(int i = 0; i < n; i++){
                // 如果将i分配到前面的组能使得这个组人数至少为A[i]，就会产生额外的1个单位收益
                if(i + 1 >= A[i]) dp[i + 1] = dp[i + 1 - A[i]] + 1;
                maxIncome = Math.max(maxIncome, dp[i + 1]);
            }
            System.out.println(maxIncome);
        }
    }
}

发表于 2021-03-14 19:11:31 回复(1)

实现梦想201807300927156

动态规划，补一个C++的，思路和上面三位一致

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int>& A,int N);


int main()
{
    int T;
    cin>>T;
    for(int i=0;i<T;i++)
    {
        int N;
        cin>>N;
        vector<int> A(N);
        for(int j=0;j<N;j++)
            cin>>A[j];
        cout<<solve(A,N)<<endl;
    }
    return 0;
}

int solve(vector<int>& A,int N)
{
//dp[i]表示从0~i-1（前i个）进行分组且i-1为所在组最后，其他单独分组，最大收益
    vector<int> dp(N+1);
    dp[0]=N;        //无分组考虑
    //初始时分成n组，收益为n
    //进行排序，尽可能满足小的A[i]以获得最大收益
    sort(A.begin(),A.end());
    int maxIncome = N;            //初始最大收益为M
    for(int i=1;i<=N;i++)
    {
        //dp转移：将i放在所在组内（如果能）组成A[i]长度，前面的从ap取得
        if(i>=A[i-1])        //最后一个放分组能得到收益+1
        {
            dp[i] = dp[i-A[i-1]]+1;    //由排序易知这一组都满足
            //如果不能放入，dp在此没有意义
            maxIncome = max(maxIncome,dp[i]);
        }
    }
    return maxIncome;
}

编辑于 2022-08-13 14:30:00 回复(0)

JCoder

来个图上DP的解法吧

将整个数组倒排(降序排序)，然后遍历：

我的目的要么就是更大的单独分组，例如 {100} {1} 。

要么就是尽量满足更大的，例如 {4, 4, 4, 4} {1} 。

如果大的单独分组，则相当于大的没得到满足，贡献只增加了 1，也就是这一组的组贡献。

如果大的不单独分组，则相当于大的满足了，大的都满足了，同组内小的也能满足，也就是说贡献变成了组的大小+组贡献，组的大小就是大的数字的值，组贡献是 1，即总贡献为 a[i] + 1

以下用样例 {2 3 4 1 3 2} 进行解释：

{2 3 4 1 3 2} 排序后为 {4 3 3 2 2 1}

将贡献看成边权，将分组情况看成边（组的第一个元素指向下一个组的第一个元素），可以得到下面的图：

权值为 1 的边代表让当前的 a[i] 单组分组的贡献，其他的边表示满足 a[i] 的组的贡献

这时候我们的目的就是求出最长路的长度，起点为 1 且终点为 n+1，可以用SPFA 加边权取相反数等办法求这个最长路。

但是有更好的办法，这个图有一个特点：所有的边的起点一定小于终点。既然不存在环，就可以考虑使用DP求解了，此时设 dp[i] 为从 i 走到 n+1 的最长路，dp[n+1] = 0，倒着推出 dp[1] 就可以得到最长的路径了。

上图的最长路有好几个：

1 -> 2 -> 5 -> 7

1 -> 5 -> 7

1 -> 2 -> 3 -> 6 -> 7

其实就分别对应了分组的状况：

{4} {3, 3, 2} {2, 1} = 1 + (3 + 1) + (2 + 1) = 8

{4, 3, 3, 2} {2, 1} = (4 + 1) + (2 + 1) = 8

{4} {3} {3, 2, 2} {1} = (1) + (1) + (3 + 1) + (1) = 8

那为什么没有题目样例解释中的分配方案 {4, 3, 3, 2, 2} {1} 呢？

这里要注意的是，这个样例的方案，最后一个 2 就算是放到后面的组内，也会产生自己的贡献。

相当于这个 2 在第一组是凑数的，因为最大的 4 已经满足了，所以进来的数字不管是啥都会产生自己的贡献，在图中这种边是可以存在的，但是对答案没有影响。假设这条边存在，那么应该是 a[1] = 4 连接到 a[6] = 1，边权为组大小+组贡献，为 5+1 = 6。但是会发现，图中已经存在了 a[1] 到 a[5] 的权值为 5 的边，以及 a[5] 到 a[6] 权值为 1 的边，也是 5+1 = 6，所以这条理论上长为 6 的边是没有意义的。

但是如果这个 2 变成 1，结果就不同了，因为 1 可以自己分组了，并且图也会产生相应的变化。

#include <bits/stdc++.h>
using namespace std;

int n, T, a[100005], dp[100005];
vector<pair<int, int> > e[100005];
int main() {
    scanf("%d", &T);
    while (T--) {
        for (int i = 0; i <= n + 1; i++) {
            e[i].clear();
        }
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        sort(a + 1, a + n + 1, greater<int>());
        for (int i = 1; i <= n; i++) {
            e[i].push_back(make_pair(i + 1, 1));
            if (a[i] + i <= n + 1) {
                e[i].push_back(make_pair(a[i] + i, a[i] + 1));
            }
        }

        dp[n + 1] = 0;
        for (int i = n; i >= 1; i--) {
            dp[i] = 0;
            for (int j = 0; j < e[i].size(); j++) {
                dp[i] = max(dp[i], dp[e[i][j].first] + e[i][j].second);
            }
        }
        printf("%d\n", dp[1]);

    }

    return 0;
}

编辑于 2021-08-18 17:11:32 回复(0)

Python

顺利上岸吧求求了

首先将给定的A按升序排序。以为总收益为分组数加额外收益，而每个人都可看做一组，所以可以换个角度考虑，将总收益看作人数加所分得做多非1人组的个数，且每一组满足人数大于等于该组中最大的A[i]。于是利用零葬的idea，

dp[i + 1] = dp[i + 1 - A[i]] + 1 (i + 1 >= A[i])

显然i+1-A[i]到第i个人的总人数为A[i]，可分为1组于是+1。dp[i+1]为对0到i进行上述分组（并且其中第i个数为最后一个分组的最后一个数）的结果。例如122336中，dp[2]=dp[2-A[1]]+1=n+1，表示分组为12，2，3，3，6的结果，而dp[6]=dp[6-6]+1,表示分组为122336的结果。

t=int(input())
while t:
    t-=1
    n=int(input())
    a=list(map(int, input().strip().split()))
    a.sort()
    res=n
    dp=[0 for _ in range(n+1)]
    dp[0]=n
    for i in range(n):
        if i+1>=a[i]:
            dp[i+1]=dp[i+1-a[i]]+1
            res=max(res, dp[i+1])
    print(res)

发表于 2022-03-28 15:53:51 回复(0)