POJ-3536: Beer Refrigerator

keyword

BruteForce　C++

問題概要

N(<10^6)が与えられる。体積がNになるような直方体で、表面積が最小になるような３辺の長さを求める問題。

解法

３辺をa,b,cと置く。a<=b<=cを仮定すると全探索が間に合う。何故なら、aの候補はcbrt(N)以下のNの約数で、M=N/aと置くとbの候補はsqrt(M)以下だから。cbrt(N)以下の約数の個数はそんなに多くないので、計算量はO(sqrt(N))より微妙に大きいかもしれないというレベル。
相加相乗平均を使うと３つの和の任意の２つの差の平方の和が最小になるようにとか、そういう数学的な解法もあるかもしれないけど、間に合うならばBruteForce(というか、一番分かりやすい書き方)が一番優れていると思う。

#include <cstdio>
using namespace std;

int N;

void solve(){
	int ta, tb, tc;
	int best = 1<<30;
	for(int a=1; a*a*a<=N; a++)if(N%a==0){
		int M = N/a;
		for(int b=a; b*b<=M; b++)if(M%b==0){
			int c = M/b, t = a*b + b*c + c*a;
			if(t < best){
				best = t;
				ta = a;
				tb = b;
				tc = c;
			}
		}
	}
	printf("%d %d %d\n", ta, tb, tc);
}

int main(){
	scanf("%d",&N);
	solve();
	return 0;
}