Packets
描述
一家工厂生产产品，这些产品被包装在高度相同为 ( h ) 的正方形包装中，产品的尺寸分别为：1×1、2×2、3×3、4×4、5×5、6×6。
这些产品最终都被运送给客户，运输时使用的包装箱同样具有高度 ( h )，并且箱子的尺寸固定为 6×6。
由于运输费用较高，工厂和客户都希望尽量减少运输所需的箱子数量。
你的任务是编写一个程序，计算在满足装箱要求的前提下，最少需要多少个 6×6 的箱子来装下给定订单中的所有产品。
输入
输入由多行组成，每一行表示一个订单。
每行包含 6 个整数，用空格隔开，分别表示从最小尺寸 1×1 到最大尺寸 6×6 的产品数量。
当输入行为：
0 0 0 0 0 0时，表示输入结束，该行不需要处理。
输出
对于输入的每一行订单，输出一行，表示该订单所需的最少箱子数量。
注意：最后的全零行不对应任何输出。
样例输入
0 0 4 0 0 1 7 5 1 0 0 0 0 0 0 0 0 0样例输出
2 1题解
按从大到小逐层“贪心填箱”，每一类都尽量最大化利用6×6剩余空间
| 层级 | 贪心目标 |
|---|---|
| 6×6 | 不可拆，直接占箱 |
| 5×5 | 用 1×1 填剩余空间 |
| 4×4 | 用 2×2 优先填空 |
| 3×3 | 分类讨论 把剩下空间尽可能分给2×2 然后1×1 填剩余空间 |
| 2×2 | 尽量装满 |
| 1×1 | 收尾填充 |
代码
#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);inta1,a2,a3,a4,a5,a6;while(cin>>a1>>a2>>a3>>a4>>a5>>a6){if(a1==0&&a2==0&&a3==0&&a4==0&&a5==0&&a6==0)break;intboxes=0;// 6x6boxes+=a6;// 5x5 + 1x1boxes+=a5;a1=max(0,a1-11*a5);// 4x4 + 2x2 + 1x1boxes+=a4;intspace_4=5*a4;// 每个4x4剩余5个1x1格子if(a2>=space_4){a2-=space_4;}else{space_4-=a2;a2=0;a1=max(0,a1-space_4*4);}// 3x3boxes+=(a3+3)/4;intrem3=a3%4;if(rem3){intuse2=0,use1=0;if(rem3==1){use2=5;use1=7;}elseif(rem3==2){use2=3;use1=6;}elseif(rem3==3){use2=1;use1=5;}if(a2>=use2){a2-=use2;}else{use1+=(use2-a2)*4;a2=0;}a1=max(0,a1-use1);}// 2x2boxes+=(a2+8)/9;intrem2=a2%9;if(rem2){a1=max(0,a1-(36-rem2*4));}// 1x1boxes+=(a1+35)/36;cout<<boxes<<"\n";}return0;}
