OD C卷 - 项目排期/最少交付时间

2024-08-28 01:04

本文主要是介绍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)

 

这篇关于OD C卷 - 项目排期/最少交付时间的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1113291

相关文章

go中的时间处理过程

《go中的时间处理过程》:本文主要介绍go中的时间处理过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 获取当前时间2 获取当前时间戳3 获取当前时间的字符串格式4 相互转化4.1 时间戳转时间字符串 (int64 > string)4.2 时间字符串转时间

深度解析Java项目中包和包之间的联系

《深度解析Java项目中包和包之间的联系》文章浏览阅读850次,点赞13次,收藏8次。本文详细介绍了Java分层架构中的几个关键包:DTO、Controller、Service和Mapper。_jav... 目录前言一、各大包1.DTO1.1、DTO的核心用途1.2. DTO与实体类(Entity)的区别1

Golang如何对cron进行二次封装实现指定时间执行定时任务

《Golang如何对cron进行二次封装实现指定时间执行定时任务》:本文主要介绍Golang如何对cron进行二次封装实现指定时间执行定时任务问题,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录背景cron库下载代码示例【1】结构体定义【2】定时任务开启【3】使用示例【4】控制台输出总结背景

如何在Spring Boot项目中集成MQTT协议

《如何在SpringBoot项目中集成MQTT协议》本文介绍在SpringBoot中集成MQTT的步骤,包括安装Broker、添加EclipsePaho依赖、配置连接参数、实现消息发布订阅、测试接口... 目录1. 准备工作2. 引入依赖3. 配置MQTT连接4. 创建MQTT配置类5. 实现消息发布与订阅

springboot项目打jar制作成镜像并指定配置文件位置方式

《springboot项目打jar制作成镜像并指定配置文件位置方式》:本文主要介绍springboot项目打jar制作成镜像并指定配置文件位置方式,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录一、上传jar到服务器二、编写dockerfile三、新建对应配置文件所存放的数据卷目录四、将配置文

怎么用idea创建一个SpringBoot项目

《怎么用idea创建一个SpringBoot项目》本文介绍了在IDEA中创建SpringBoot项目的步骤,包括环境准备(JDK1.8+、Maven3.2.5+)、使用SpringInitializr... 目录如何在idea中创建一个SpringBoot项目环境准备1.1打开IDEA,点击New新建一个项

springboot项目中整合高德地图的实践

《springboot项目中整合高德地图的实践》:本文主要介绍springboot项目中整合高德地图的实践,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一:高德开放平台的使用二:创建数据库(我是用的是mysql)三:Springboot所需的依赖(根据你的需求再

一文详解如何在idea中快速搭建一个Spring Boot项目

《一文详解如何在idea中快速搭建一个SpringBoot项目》IntelliJIDEA作为Java开发者的‌首选IDE‌,深度集成SpringBoot支持,可一键生成项目骨架、智能配置依赖,这篇文... 目录前言1、创建项目名称2、勾选需要的依赖3、在setting中检查maven4、编写数据源5、开启热

SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志

《SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志》在SpringBoot项目中,使用logback-spring.xml配置屏蔽特定路径的日志有两种常用方式,文中的... 目录方案一:基础配置(直接关闭目标路径日志)方案二:结合 Spring Profile 按环境屏蔽关

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五