首先,我们分析答案是否满足单调性:如果天数越大,就越容易满足条件,如果天数越小,就越不容易满足条件,因此是具备单调性的,可以使用二分答案求解。
我们二分去枚举最终的天数x,判断这N个人是否能在x天内完成所有的任务,其实就是看能否把这些任务分成至多N组,而且每一组的份数都不超过x。
判断的方式我们采用DFS+剪枝的做法处理,其实就是把它抽象为m个物品能否放到N个盒子中,每个盒子的容纳体积上限为x。
项目组共有N个开发人员,项目经理接到了M个独立的需求,每个需求的工作量不同,且每个需求只能由一个开发人员独立完成,不能多人合作。
假定各个需求直接无任何先后依赖关系,请设计算法帮助项目经理进行工作安排,使整个项目能用最少的时间交付。
第一行输入为M个需求的工作量,单位为天,用逗号隔开。
例如:
X1 X2 X3 ... Xm 表示共有M个需求,每个需求的工作量分别为X1天,X2天,…,Xm天。其中:
0 < M < 30 0 < Xm < 200 第二行输入为项目组人员数量N,
例如:
5 表示共有5名员工,其中0 < N < 10
输入
6 2 7 7 9 3 2 1 3 11 4
2
输出
28