SRM507 Div1 Medium(500) CubePacking

TopCoder

CubePacking

幅＜高さ＜奥行き　として、幅と高さを全探索。間に合う。幅と高さをどちらもLにすれば、ceil(総体積/(L*L))の立方体には収まるので、答えはそれ以下。

#include <algorithm>
using namespace std;

class CubePacking{public:
int getMinimumVolume( int Ns, int Nb, int L )
{
    long long V = Ns+Nb*L*L*L;          //  総体積
    long long ans = V+L*L*L;
    for ( long long w=L; w*w*w<V+L*L*L; w++ )
    for ( long long h=L; w*h*h<V+L*L*L; h++ )
    {
        long long a = (w/L)*(h/L);      //  サイズLの立方体の底面の個数
        long long d1 = (Nb+a-1)/a*L;    //  サイズLの立方体を詰めるのに必要な高さ
        long long d2 = (V+w*h-1)/(w*h); //  全ての立方体を詰めるのに必要な高さ
        long long d = max(d1,d2);
        ans = min( ans, w*h*d );
    }
    return (int)ans;
}};