题意：给定Ns个1*1*1的方块和Nb个L*L*L的方块，求一个体积最小的长方体，可以把所有的方块都装在里面。(1<=Ns<=10^9,1<=Nb<=10^6,2<=L<=10)
解法：首先考虑矩形体积最大能是多少。体积为1的方块最多能有10^9个，所以总体积是10^9。体积为10^3的方块最多能有10^6个，总体积也是10^9。合在一起体积为2*10^9，没有超过int范围，而且可以证明其它数据求出的长方体体积也不会超过这个范围。所以可以设LIMIT=2*10^9。接下来我们可以枚举长方体的长和宽，然后根据长和宽，在O(1)的时间里求出长方体的高(长宽高分别是x,y,z)，这一步我们可以假设(x<=y<=z)。由于x*y*z<=LIMIT，所以总时间复杂度是O(LIMIT^(2/3))。
#include <algorithm>
using namespace std;
const long long LIMIT = 2000000000;
class CubePacking {
public:
int getMinimumVolume(int Ns, int Nb, int L) {
long long x, y, z, s, n, res, Vb;
Vb = Nb * L * L * L;
res = LIMIT;
for (x = L; x * x * x <= LIMIT; x++) {
for (y = x; x * y * y <= LIMIT; y++) {
n = (x / L) * (y / L);
z = ((Nb + n - 1) / n) * L;
s = Ns - (x * y * z - Vb);
if (s > 0)
z += (s + x * y - 1) / (x * y);
if (z < y)
break;
if (x * y * z < res)
res = x * y * z;
}
}
return (int)res;
}
};