c110 - 00311 - Packets
題目描述
題目描述了工廠將不同尺寸的正方形產品 (1x1 到 6x6) 打包成 6x6 的箱子運送給客戶，目標是計算最少需要的箱子數量。輸入為六個整數，分別代表各個尺寸產品的數量。當所有產品數量都為 0 時，輸入結束。
解題思路
這題的核心是貪心策略。程式碼按照優先順序嘗試將較大的正方形放入箱子中，以最大化每個箱子的利用率。具體步驟如下：
- 首先，盡可能放入 5x5 的正方形。
- 然後，盡可能放入 4x4 的正方形。
- 接著，盡可能放入 3x3 的正方形。
- 然後，盡可能放入 2x2 的正方形，並處理剩餘空間。
- 最後，盡可能放入 1x1 的正方形，並處理剩餘空間。
程式碼模擬了這個打包過程，並計算所需的箱子數量。
複雜度分析
- 時間複雜度: O(1)
- 空間複雜度: O(1)
程式碼
#include <iostream>
using namespace std;
int a[6];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> a[0]){
int ans=0,s=0;
for(int i=1;i<6;++i){
cin >> a[i];
s+=a[i];
}
if(s+a[0]==0)break;
ans+=a[5];
ans+=a[4];
a[0]-=a[4]*11;
ans+=a[3];
a[1]-=a[3]*5;
ans+=a[2]/4;
a[2]%=4;
if(a[2]){
ans+=1;
int re=4-a[2];
a[1]-=re*2-1;
a[0]-=(36-a[2]*9-(re*2-1)*4);
}
if(a[1]<0){
a[0]-=a[1]*-2;
a[1]=0;
}
if(a[1]>0){
ans+=a[1]/9;
a[1]%=9;
}
if(a[1]>0){
++ans;
a[0]-=(36-a[1]*4);
}
if(a[0]>0){
ans+=a[0]/36;
a[0]%=36;
}
if(a[0]>0){
++ans;
}
cout << ans << '\n';
}
}