首页 > 代码库 > poj 1017(贪心）

poj 1017(贪心）

2024-07-15 05:44:22   220人阅读

【题目大意】

题目大意是这样的：某工厂生产几种产品，首先用packet包住，这些产品的高度都是h，底面积有1*1,2*2,3*3,4*4,5*5,6*6六种规格，下面我们要用高度为h，底面积为6*6的集装箱装这些货物，问怎样使所用集装箱数目最少？

【解题思路】

我们首先必须先装底面积大的货物，并且对于面积为4*4,5*5，6*6的货物，每一件都需要一个独立的集装箱。对于底面积为3*3的货物，每四个需要一个集装箱。

那么我们可以得知对于装了底面积为3*3的货物的集装箱，其剩余可以装5,3,1个底面积为2*2的货物。对于装了底面积为4*4的集装箱，其剩余空间可以装5个2*2的货物。对于装了底面积为5*5的集装箱，其剩余可以装11个底面积为1*1的集装箱。我们可以通过计算剩余的空间进而求得最小数目。

【AC代码】

 1 #include <stdio.h> 2 int  main() 3 { 4  int N, a, b, c, d, e, f, y, x; 5  int u[4]={0, 5, 3, 1}; 6  while(1) 7  { 8   scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f); 9   if (a == 0 && b == 0 && c == 0 && d == 0 && e == 0 && f == 0) break;10   N = f + e + d + (c + 3) / 4;//向上取整11   y = 5 * d + u[c % 4];12   if(b > y) N += (b - y + 8 ) / 9;13   x = 36 * N - 36 * f - 25 * e - 16 * d - 9 * c - 4 * b;14   if(a > x) N += ( a - x + 35 ) / 36;15   printf("%d\n", N);16  }17  return 0;18 }

 


联系
我们