Software
发布日期:2022-02-05 18:27:28 浏览次数:14 分类:技术文章

本文共 1736 字,大约阅读时间需要 5 分钟。

【题目背景】

一个软件开发公司同时要开发两个软件,并且要同时交付给用户,现在公司为了尽快完成这一任务,将每个软件划分成m个模块,由公司里的技术人员分工完成,每个技术人员完成同一软件的不同模块的所用的天数是相同的,并且是已知的,但完成不同软件的一个模块的时间是不同的,每个技术人员在同一时刻只能做一个模块,一个模块只能由一个人独立完成而不能由多人协同完成。一个技术人员在整个开发期内完成一个模块以后可以接着做任一软件的任一模块。写一个程序,求出公司最早能在什么时候交付软件。

【输入格式】

输入文件第一行包含两个由空格隔开的整数nm,其中1≤n≤100,1≤m≤100。接下来的n行每行包含两个用空格隔开的整数d1和d2,d1表示该技术人员完成第一个软件中的一个模块所需的天数,d2表示该技术人员完成第二个软件中的一个模块所需的天数,其中1d1,d2≤100

【输出格式】

输出文件仅有一行包含一个整数d,表示公司最早能于d天后交付软件。

【样例】

SOFTWARE.IN

3  20

1 1

2 4

1 6

SOFTWARE.OUT

18

【样例解释】

最快的方案是第一个技术人员完成第二个软件的18个模块,用时18天,第三个技术人员完成第一个软件的18个模块,用时18天,其余的模块由第二个技术人员完成,用时12天,做完所有的模块需要18天。如果第一个技术人员完成第二个软件的17个模块,第三个技术人员完成第一个软件的17个模块,其余的模块由第二个技术人员完成,需要用时18天,做完所有模块仍然需要18天,所以少于18天不可能做完所有模块。

曾经做过一个加工生产调度的题 感觉有点像 但死活还是不会做

我个弱b...

到死也没做出来

听了讲解 是二分+DP验证

二分答案想到了 但是不会验证

令f[i][j]表示前i个人做第一个软件j个模块时  可以做第二个软件模块数的最大值

二分时间限制

判断f[时间][模块数]是否大于模块数

如果大于 在l和mid间寻找答案

否则在mid+1和r间寻找答案

dp时注意细节

f[0][0]=0;f[0][1]=-inf;......

#include
#include
#include
using namespace std;const int inf=999999999;struct self{int x,y;}s[111];int m,n,mid,l,r,a,b,c;int ans;int f[111][111];int work(int i,int j){ if(i<0||j<0)return -inf; if(f[i][j]!=-1)return f[i][j]; f[i][j]=work(i-1,j)+mid/s[i].y; for(int a=j-1;a>=0&&s[i].x*(j-a)<=mid;a--) f[i][j]=max(f[i][j],work(i-1,a)+(mid-s[i].x*(j-a))/s[i].y); return f[i][j];}int main(){ scanf("%d%d",&m,&n); for(a=1;a<=m;a++)scanf("%d%d",&s[a].x,&s[a].y); l=0;r=10000; while(l<=r) { mid=(l+r)>>1; memset(f,-1,sizeof(f)); f[0][0]=0; for(a=1;a<=n;a++)f[0][a]=-inf; work(m,n); if(f[m][n]>=n) { r=mid-1; ans=mid; } else { l=mid+1; } } cout<
<<'\n'; return 0;}

转载地址:https://blog.csdn.net/li412302070/article/details/12977727 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:COGS 1266 借教室
下一篇:TYVJ 1434 黑匣子

发表评论

最新留言

网站不错 人气很旺了 加油
[***.192.178.218]2024年03月22日 04时03分13秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

java jdk win10 1335_win10下安装java jdk,tomcat 2019-04-21
java list二分查找_java中的ArrayList和LinkedList的二分查找速度比 | 学步园 2019-04-21
php中的变量名称用什么表示,PHP变量,方法,类等名称中的有效字符是什么? 2019-04-21
pic32mx是什么cpu_PIC32MX单片机外设库使用(Ⅰ)- 系统时钟及I/O口基本设置 2019-04-21
用c 在mysql上存图片_C 批量保存图片进 mysql 利用MYSQL_BIND插入longblob 2019-04-21
mysql 1045 28000_mysql报关于用户密码1045(28000),几种处理方法 (zhuan) 2019-04-21
solr比mysql的优势_Solr与Elasticsearch的优缺点比较总结和归纳 2019-04-21
华为博士招聘上机考试题目_牛客网-华为-2020届校园招聘上机考试-3 2019-04-21
python中for可以做变量名吗_Python中使用动态变量名的方法 2019-04-21
mysql 日期转换天数_MySQL 日期操作 增减天数、时间转换、时间戳 2019-04-21
java对象去重复_JAVA中List对象去除重复值的方法 2019-04-21
java bss_[转] .bss段和.data段的区别 2019-04-21
java上传图片损坏_大神求助 上传图片后 图片损坏 2019-04-21
java socket唯一标识符_Java Socket编程之常识网络基础知识 2019-04-21
java给xyz大小排序_java递归实现string xyz排序 2019-04-21
arctime必须要java_Arctime使用教程 Arctime常见问题解答 2019-04-21
mysql pxc mysql5.7_mysql之PXC5.7.18集群系列——1. Percona XtraDB Cluster 搭建 2019-04-21
mysql 自适应字段宽度_box-sizing解决自适应布局容器宽度问题 2019-04-21
java 配置文件配置路径_Java读取配置文件路径设置 2019-04-21
vux 选择器_vue中的scoped分析以及在element-UI和vux中的应用 2019-04-21