OD C卷 - 项目排期/最少交付时间
项目排期/最少交付时间（200）
- m个独立的需求，由n个开发者完成；
- 每个任务都是独立的，只能由一个人完成；
- 计算项目最少的交付时间；
输入描述：
第一行输入m个需求的工作量（天数），m在(0,30)之间，每个需求的天数<200
第二行输入人员数量n
输出描述:
项目最少的交付时间
示例1
输入：
6 2 7 7 9 3 2 1 3 11 4
2
输出：
28
示例2
输入：
2 3 4 2 5
3
输出：
6
示例3
输入：
100 50 30 10
3
输出：
100
思路：
- 二分求解
- 需求的工作量升序排序；
- 取完成需求的最小天数，计为 left = sum // n ；
- 取一个人完成时耗费的天数为最大，计为 right = sum；
- 二分法取 mid = (left + right) // 2，判断在这个mid以内是否能够在n个人之间完成需求的分配（每个人完成需求的天数<=mid）；
- 若可以完成分配，则进一步减少天数，令result = mid; right = mid-1; 否则 left=mid+1；
- 需求的分配是从需求天数最小开始，依次分配给n个人，若给一个人分配后，其完成天数超出mid阈值，则将当前需求分配给下一个人
- 最后求得result
result = -1class MinimumTime:def solution(self, req_days, n):# 总天数total = sum(req_days)self.m = len(req_days)self.req_days = req_days# 分配需求的数组self.jobs = [0 for i in range(n)]# 需求工作量 排序req_days.sort()# 最小天数left = total // n# 最大天数right = total# 依次求解global resultwhile left <= right:print("left:", left)print("right:", right)mid = (left + right) // 2print("mid:", mid)# 清空jobsfor i in range(n):self.jobs[i] = 0# 是否可以成功分配if self.align_req(0, mid):print("成功:")result = midright = mid - 1else:print("失败:")left = mid + 1# low与最大的需求天数对比# print(low if low > req_days[-1] else req_days[-1])def align_req(self, days_idx, threshold):# 递归分配任务global nif days_idx >= self.m:# 分配完成return Truei = 0 # 依次分配给n个人while True:if i >= n:breakelse:total_v = self.req_days[days_idx] + self.jobs[i]if total_v > threshold:if self.jobs[i] == 0: # 还没分配 就超出阈值breakelse:# 需求到开发 成功分配self.jobs[i] += self.req_days[days_idx]# 按照当前阈值，继续分配下一个需求if self.align_req(days_idx + 1, threshold):return True# 下一个需求无法完成分配，当前分配撤销self.jobs[i] -= self.req_days[days_idx]i += 1return Falseif __name__ == '__main__':mini_time = MinimumTime()req_days = list(map(int, input("days:").strip().split()))n = int(input("n:").strip())mini_time.solution(req_days, n)print(result)