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

这是qklbishe.com第7783 篇笔试面试资料
提供答案分析,通过本文《小美要将N 名员工分成若干组,且每组至少要有一名员工。每个组都会产生一个单位的收益,且对于第i 名员工,如果其所在的组包含至少A[i] 名员工(包括第i 名员工自身),则该员工会额外贡献一个单位的收益。现在,小美请小团将N 名员工分组,使得总收益最大。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

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

小美要将N 名员工分成若干组,且每组至少要有一名员工。每个组都会产生一个单位的收益,且对于第i 名员工,如果其所在的组包含至少A[i] 名员工(包括第i 名员工自身),则该员工会额外贡献一个单位的收益。现在,小美请小团将N 名员工分组,使得总收益最大。 零葬
由于员工i所在的组至少要有A[i]人才能获得额外的一个收益,而不管A[i]是多少,达到这个人数后额外收益也只会是一个单位,因此为了获得额外的那个收益,应该尽可能先满足A[i]小的,这样获得额外收益的门槛更低。
先对A进行升序排列,然后利用动态规划求解,因为每人自成一组的情况下可以获得n个收益,因此初始化收益为ndp[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 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 小美要将N 名员工分成若干组,且每组至少要有一名员工。每个组都会产生一个单位的收益,且对于第i 名员工,如果其所在的组包含至少A[i] 名员工(包括第i 名员工自身),则该员工会额外贡献一个单位的收益。现在,小美请小团将N 名员工分组,使得总收益最大。-笔试面试资料

提供最优质的资源集合

立即查看 了解详情