d502 - 第三題：產品包裝

🔗 前往 ZeroJudge 原題

題目描述

題目描述了工廠生產四種不同邊長的正立方體產品，並要求計算滿足訂單所需的最小包裝箱數量。包裝箱的尺寸固定為 4x4x4 公分。輸入為四種產品的數量，輸出為所需的最小包裝箱數量。

解題思路

這題的核心在於如何有效地將不同尺寸的立方體產品放入固定尺寸的包裝箱中，以最小化所需的包裝箱數量。程式碼採用貪心策略，首先計算邊長為 1 的產品所需的包裝箱數量，然後計算邊長為 2 的產品所需的包裝箱數量，以此類推。

對於邊長為 1 的產品，每 64 個可以放入一個 4x4x4 的包裝箱。對於邊長為 2 的產品，每 8 個可以放入一個 4x4x4 的包裝箱。邊長為 3 和 4 的產品則直接加到總包裝箱數中。

程式碼首先計算邊長為 1 的產品所需的包裝箱數量，然後計算邊長為 2 的產品所需的包裝箱數量，最後將所有包裝箱數量加總，得到最終結果。

複雜度分析

• 時間複雜度: O(1)
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
int main(){
	int a,b,c,d;
	while(cin >> a >> b >> c >> d){
		int k=0;
		a-=37*c+(b%8)*8;
		if(b>0){
			k+=(b/8+1);
			if(b%8==0)
				k--;	
		}
		if(a>0){
			k+=(a/64+1);
			if(a%64==0)
				k--;
		}
		cout << d+c+k << "\n";
	}
}