首页 > 代码库 > HDU----(4519)郑厂长系列故事——体检
HDU----(4519)郑厂长系列故事——体检
郑厂长系列故事——体检
Time Limit: 500/200 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1097 Accepted Submission(s): 596
Problem Description
郑厂长不是正厂长
也不是副厂长
他根本就不是厂长
只是公司的一个码农
郑厂长所在的腾讯公司每一年都要组织员工体检,比如量身高体重、测血压之类的,今年也不例外。
这次总共有N位员工接受体检,并且每个员工都需要做K个项目的检查才算完成整个体检的流程。现在来了M个医生为员工做身体检查,并且每一位医生都带齐了检查这K个项目的器材来(也就是说每个医生都能进行这K个项目中的任意一项检查)。
体检的详细流程是这样的:
公司事先制定好了M份体检单,每个医生手上都各自拿到一份体检单,上面已经安排好了检查的次序,以及每一次检查所对应的员工和项目。每个医生按照体检单上的次序为相应的员工做相应的项目检查。医生拿到的体检单上的名单也可以是空的,就是这个医生不需要检查任何员工的任何项目。
当然,制定出的这M份体检单不能有问题存在,否则就会有混乱的情况发生。按照常理来说,同一个医生在同一时间只能为一个员工做一个项目的检查。另外,同一个员工在同一时间也只能进行一个项目的检查,当然,不同的医生或不同的员工可以在同一时间进行项目检查。现在假设每个员工的每个项目的检查时间都是一分钟(其它时间花费忽略不计,只考虑项目检查工作所花费的一分钟)。
公司希望体检的工作越快完成越好,由于郑厂长大学期间曾经是一个ACMer,所以公司就将体检的安排工作交给了他,他需要计算出最快需要多少分钟能完成所有员工的体检工作。
也不是副厂长
他根本就不是厂长
只是公司的一个码农
郑厂长所在的腾讯公司每一年都要组织员工体检,比如量身高体重、测血压之类的,今年也不例外。
这次总共有N位员工接受体检,并且每个员工都需要做K个项目的检查才算完成整个体检的流程。现在来了M个医生为员工做身体检查,并且每一位医生都带齐了检查这K个项目的器材来(也就是说每个医生都能进行这K个项目中的任意一项检查)。
体检的详细流程是这样的:
公司事先制定好了M份体检单,每个医生手上都各自拿到一份体检单,上面已经安排好了检查的次序,以及每一次检查所对应的员工和项目。每个医生按照体检单上的次序为相应的员工做相应的项目检查。医生拿到的体检单上的名单也可以是空的,就是这个医生不需要检查任何员工的任何项目。
当然,制定出的这M份体检单不能有问题存在,否则就会有混乱的情况发生。按照常理来说,同一个医生在同一时间只能为一个员工做一个项目的检查。另外,同一个员工在同一时间也只能进行一个项目的检查,当然,不同的医生或不同的员工可以在同一时间进行项目检查。现在假设每个员工的每个项目的检查时间都是一分钟(其它时间花费忽略不计,只考虑项目检查工作所花费的一分钟)。
公司希望体检的工作越快完成越好,由于郑厂长大学期间曾经是一个ACMer,所以公司就将体检的安排工作交给了他,他需要计算出最快需要多少分钟能完成所有员工的体检工作。
Input
输入的第一行为一个正整数T,表示有T组测试数据;
接下去有T组测试数据,每组测试数据占一行,包含三个整数N,K,M,N表示员工的人数,K表示体检的项目数,M表示医生的人数。
[Technical Specification]
T<=1000
1<=N<=100
1<=K<=10
1<=M<=100
接下去有T组测试数据,每组测试数据占一行,包含三个整数N,K,M,N表示员工的人数,K表示体检的项目数,M表示医生的人数。
[Technical Specification]
T<=1000
1<=N<=100
1<=K<=10
1<=M<=100
Output
对于每组数据,输出一个整数,表示最快需要多少分钟才能完成所有员工的体检工作。
Sample Input
22 1 13 2 2
Sample Output
23
Hint
对于第二组数据体检单的安排可以是如下情况:第1个医生的体检单:员工A的项目1、员工A的项目2、员工B的项目2;第2个医生的体检单:员工B的项目1、员工C的项目1、员工C的项目2。第一分钟:第1个医生检查员工A的项目1,而第2个医生检查员工B的项目1;第二分钟:第1个医生检查员工A的项目2,而第2个医生检查员工C的项目1;第三分钟:第1个医生检查员工B的项目2,而第2个医生检查员工C的项目2;这样就只需要3分钟即可完成体检工作。
Source
2013腾讯编程马拉松初赛第三场(3月23日)
题目其实不是很水的,关键在于这道题的事项,相当于一道机器调度问题,(个人感觉特别想流水线问题的简化)
分析一下这道题的态势,只要尽可能的使m(不管是医生还是机器)处于一种饱和状态下运行即可。
那么对于 n<=m的情况,其实分析就可以知道,只需要k分钟。
那么对于相对于复杂一点的n>m,我们就要考虑较多的情况。其实手写一个列子就可以很清楚的知道了:
比如: 4 4 3
4 4 4 4 面对三台机器:
1分钟: 3 3 3 4
2 分钟:2 2 3 3
3 分钟: 1 2 2 2
4 分钟: 1 1 1 1
5分钟: 1 0 0 0
6分钟: 0 0 0 0 所以结果为 6分钟
不知道发现没有,其实周期是 n 同时项目剩余未k-m;
然后我们其实可以得出
if n*k%m!=0
(n*k)/m +1;
else
(n*k)/m
当然你也可以去模拟计算....
代码:
1 #include<cstdio> 2 int main() 3 { 4 int t,n,m,k; 5 scanf("%d",&t); 6 while(t--){ 7 scanf("%d%d%d",&n,&k,&m); 8 int ans=0; 9 if((n*k)%m) ans=1;10 if(n>=m)printf("%d\n",ans+((n*k)/m));11 else printf("%d\n",k);12 }13 return 0;14 }
HDU----(4519)郑厂长系列故事——体检
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。