学步园

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=452

解题思路：

这道题是topcoder的一次比赛题目，但是数据太水，暴力可过。3层循环无压力。

但是如果是正规做法，应该是先将n开3次方，因为要3个数的和最小，所以3个数越接近越好（这貌似是个定理，不过不知道名字，就是知道而已），然后，如果找到这个数，剩下的就是n/k，这时，我们需要将n/k开方，同样找到2个最接近的数，这样3个数就是最小的。本来想的是第一次找到的一定是最小的，但是却返回一个WA，比如116，正确答案是2×2×29，而按照上面方法得到的是1×4×29，这样，我暂时是找到答案不跳出，而是继续遍历，将循环遍历之后维护ans使之最小。

暴力代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<climits>
#include<cstdlib>
#include<algorithm>
using namespace std;

int main()
{
	int n;
	int res;
	while(scanf("%d", &n) != EOF)
	{
		res = n + 2;
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= n; ++j)
				for(int k = 1; k <= n; ++k)
				{
					if(i * j * k > n)
						break;
					else if(i * j * k == n)
						res = min(res, i + j + k);
				}
		printf("%d\n", res);
	}
	return 0;
}

优化方法如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<climits>
#include<cstdlib>
#include<algorithm>
using namespace std;

const double INF = 0.000005;

double three_root(double n) //牛顿迭代法求三次方根
{
	double x = n;
	while(fabs(x * x * x - n) >= INF)
		x = (2 * x * x * x + n) / (3 * x * x);
	return (x);
}

int main()
{
	int i, j, temp;
	int ans;
	double n;
	while(scanf("%lf", &n) != EOF)
	{
		ans = n + 2;
		temp = floor(three_root(n));
		for(i = temp; i > 0; --i)
		{
			if((int)n % i == 0)
			{
				for(int j = sqrt((double)((int)n / i)); j > 0; --j)
				{
					if((int)n / i % j == 0)
					{
						ans = min(ans, i + j + (int)n / i / j);
						break;
					}
				}
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}