題意：

一個工廠制造的產品形狀都是長方體盒子，它們的高度都是 h，長和寬都相等，一共有六個型號，分別為1*1, 2*2, 3*3, 4*4, 5*5, 6*6。

這些產品通常使用一個 6*6*h 的長方體箱子包裝然后郵寄給客戶。因為郵費很貴，所以工廠要想方設法的減小每個訂單運送時的箱子數量BoxNum。

解題思路：

貪心思想：

1）6*6、5*5、4*4的肯定是一個裝一個箱子；

2）5*5里面最多再裝11個1*1的箱子；

3）4*4里面最多再裝5個2*2的箱子或者20個1*1的箱子；

4）4個3*3可以用一個箱子裝，剩下多出一個箱子里面先裝滿2*2的再裝1*1的；

5）9個2*2的可以用一個箱子裝，剩下多出來的一個箱子就把1*1的裝滿；

6）最后再把1*1的裝滿即可。

其實這道題的想法比較簡單，就是要討論的情況太多了

AC:

#include<iostream> #include<cstdio> #include<cstring> using namespace std;int num[10],three[4] = {0,5,3,1}; int main() {while(true){for(int i = 1; i <= 6; i++)scanf("%d",&num[i]);if(num[1] == 0 && num[2] == 0 && num[3] == 0 && num[4] == 0 && num[5] == 0 && num[6] == 0) break;int ans = num[6]; //6*6的必須每個占用一個箱子ans += num[5] + num[4]; //5*5和4*4的必須占用一個箱子if(num[5] * 11 >= num[1]) //5*5裝完還能裝1*1的，4*4的裝完還能裝1*1和2*2的num[1] = 0;else num[1] = num[1] - num[5]*11; //裝完5*5后空著的裝1*1后還剩下的1*1的個數if(num[4] * 5 >= num[2]){int leave = num[4]*5 - num[2]; //裝完4*4，再裝2*2后，剩下空著的還能夠裝多少個2*2的num[2] = 0;if(4*leave >= num[1])num[1] = 0;else num[1] = num[1] - 4*leave;}else num[2] = num[2] - num[4]*5; //裝完4*4，再裝2*2后，多余的2*2的個數ans += num[3] / 4; //4個3*3的可能填滿一個箱子,剩下的再拿一個箱子裝num[3] = num[3] % 4; //剩下的3*3的個數if(num[3] > 0){ans++;int s = 36 - 9*num[3] - 4*min(three[num[3]],num[2]); //裝完剩下的3*3后剩下的面積用2*2的先去填充；num[2] -= three[num[3]];if(num[2] < 0) num[2] = 0;if(num[1] <= s) //剩下的用1*1去填充num[1] = 0;else num[1] -= s;}ans += num[2] / 9; //剩下的2*2，9個可裝滿一箱子num[2] = num[2] % 9;if(num[2] > 0){ans++;int s = 36 - 4*num[2]; //剩下的面積用1*1的去填充if(s >= num[1])num[1] = 0;else num[1] = num[1] - s;}ans += num[1] / 36;num[1] = num[1] % 36;if(num[1] > 0) ans++;printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的poj 1017的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。