[C] 2013腾讯马拉松初赛 ACM 郑厂长系列故事——体检 →→→→→进入此内容的聊天室

来自 , 2020-07-09, 写在 C, 查看 96 次.
URL http://www.code666.cn/view/3837a451
  1. /*
  2.  
  3. 2013腾讯马拉松初赛第3场
  4.  
  5. 1005 郑厂长系列故事——体检
  6.  
  7. Time Limit: 1.0 Seconds   Memory Limit: 32768K
  8.  
  9.  
  10. 郑厂长不是正厂长
  11. 也不是副厂长
  12. 他根本就不是厂长
  13. 只是公司的一个码农
  14.  
  15. 郑厂长所在的腾讯公司每一年都要组织员工体检,比如量身高体重、测血压之类的,今年也不例外。
  16. 这次总共有N位员工接受体检,并且每个员工都需要做K个项目的检查才算完成整个体检的流程。现在来了M个医生为员工做身体检查,并且每一位医生都带齐了检查这K个项目的器材来(也就是说每个医生都能进行这K个项目中的任意一项检查)。
  17. 体检的详细流程是这样的:
  18. 公司事先制定好了M份体检单,每个医生手上都各自拿到一份体检单,上面已经安排好了检查的次序,以及每一次检查所对应的员工和项目。每个医生按照体检单上的次序为相应的员工做相应的项目检查。医生拿到的体检单上的名单也可以是空的,就是这个医生不需要检查任何员工的任何项目。
  19. 当然,制定出的这M份体检单不能有问题存在,否则就会有混乱的情况发生。按照常理来说,同一个医生在同一时间只能为一个员工做一个项目的检查。另外,同一个员工在同一时间也只能进行一个项目的检查,当然,不同的医生或不同的员工可以在同一时间进行项目检查。现在假设每个员工的每个项目的检查时间都是一分钟(其它时间花费忽略不计,只考虑项目检查工作所花费的一分钟)。
  20. 公司希望体检的工作越快完成越好,由于郑厂长大学期间曾经是一个ACMer,所以公司就将体检的安排工作交给了他,他需要计算出最快需要多少分钟能完成所有员工的体检工作。
  21.  
  22. Input
  23.  
  24. 输入的第一行为一个正整数T,表示有T组测试数据;
  25. 接下去有T组测试数据,每组测试数据占一行,包含三个整数N,K,M,N表示员工的人数,K表示体检的项目数,M表示医生的人数。
  26.  
  27. [Technical Specification]
  28. T<=1000
  29. 1<=N<=100
  30. 1<=K<=10
  31. 1<=M<=100
  32.  
  33. Output
  34.  
  35. 对于每组数据,输出一个整数,表示最快需要多少分钟才能完成所有员工的体检工作。
  36.  
  37.  
  38. Sample Input
  39.  
  40. 2
  41. 2 1 1
  42. 3 2 2
  43.  
  44. Sample Output
  45.  
  46. 2
  47. 3
  48.  
  49. Hint:
  50. 对于第二组数据体检单的安排可以是如下情况:
  51. 第1个医生的体检单:员工A的项目1、员工A的项目2、员工B的项目2;
  52. 第2个医生的体检单:员工B的项目1、员工C的项目1、员工C的项目2。
  53. 第一分钟:第1个医生检查员工A的项目1,而第2个医生检查员工B的项目1;
  54. 第二分钟:第1个医生检查员工A的项目2,而第2个医生检查员工C的项目1;
  55. 第三分钟:第1个医生检查员工B的项目2,而第2个医生检查员工C的项目2;
  56. 这样就只需要3分钟即可完成体检工作。
  57.  
  58. */
  59.  
  60. /*
  61. 解题报告:
  62.  
  63. 首先看数据的组数,有一些多啊,如果是DP,那么复杂度稍稍大一些就不好过了。而且时限比较少。
  64. 应该是公式。
  65. 模拟了一下,如果m>=n那么肯定要K分钟检查,因为这个已经是最好的结果了,每一个医生有在用,每一个人都有在用。
  66.  
  67. 如果m<n,因为每一时刻我们可以调整医生查哪个人,所以可以保证每一个医生每一时刻都在工作
  68. 每一个时刻m个医生能检查m个项目。
  69.  
  70. 如果想把n个人k个项目都查完。要求ans*m>=n*k
  71.  
  72. 这样就可以求出ans了。
  73.  
  74. 转自:chenwenwen0210的百度空间
  75. */
  76.  
  77. #include<stdio.h>
  78. #include<string.h>
  79. const int MAX = 2100;
  80. char map[MAX][MAX];
  81. int h[MAX];
  82. int calc(int n, int x, int y) {
  83.     int i, cnt = 0, j;
  84.     int ret = 0;
  85.     for(i = 0; i < n; i++) {
  86.         if(h[i] >= x) {
  87.             cnt = 0;
  88.             j = i;
  89.             while(j < n && h[j] >= x) {
  90.                 cnt++;
  91.                 j++;
  92.             }
  93.             i = j - 1;
  94.             if(cnt >= y)ret += cnt - y + 1;
  95.         }
  96.     }
  97.     return ret;
  98. }
  99. int main() {
  100.     int n, i, j;
  101.     int m;
  102.     int x, y;
  103.     int T, k;
  104.     scanf("%d", &T);
  105.     while(T--) {
  106.         scanf("%d%d%d", &n, &k, &m);
  107.         if(m >= n)printf("%d\n", k);
  108.         else    printf("%d\n", (n * k + m - 1) / m);
  109.     }
  110.     return 0;
  111. }

回复 "2013腾讯马拉松初赛 ACM 郑厂长系列故事——体检"

这儿你可以回复上面这条便签

captcha