huring
0%

51nod-1744 codeforce-143c

Posted on In

题目：
羊村的羊们为了过冬，他们要在夏天的时候存储一些食物。等到冬天时拿出来吃。他们把食物包装成1×1×1的小方块，以便存储和取出来食用。经过了一个夏天后，小羊们存储了A·B·C块食物。他们把食物放到一个长方体的小屋里，A层高，每层有B行，每行有C块食物。

在秋天过后，村长来到小屋，要打开门分发食物了。但是，很不幸，小屋的四周都散落着食物块。经过查证，小偷们从小屋的顶层，前面，后面，和侧面都偷走了一个面的食物，一个面的食物指的是紧贴着某个面食物。所以剩下只有 （𝐴−1）×（𝐵−2）×（𝐶−2） 块食物。为了隐藏罪证，小偷们把剩下的食物块，全部打乱，散落在小屋的四周。所以村长忘记了原来A，B，C到底是多少。

现在给定n，表示剩下的食物数量。计算可能最小和最大被偷走的食物数量。

样例解释：

在样例中，如果原来的数量为32＝2×4×4，现在的数量是4＝（2-1）×（4-2）×（4-2），则被偷走的是32-4＝28块。
如果原来的数量为45＝5×3×3，现在的数量是4＝（5-1）×（3-2）×（3-2），则被偷走的是45-4＝41块。

解法：
暴力遍历所有方法即可

ps：初始想法错误，初始想法是想找方差最小的ABC，即为MIN；1，1，n即为MAX；并且abc中与1相乘的越大，最终得到的结果越小，此想法为错误的。最终选择了暴力的做法。复杂度为n的2/3次方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
    int n;
    long long a[3];
    long long Min = 9999999999999999, Max = 0;
    scanf("%d",&n);
    long long x = pow(n, 1.0/3);
    for(int i = 1; i <= x; i++)
    {
        int p = n;
        if(p % i == 0)
        {
            p /= i;
            a[0] = i;
            int k = sqrt(p);
            for(int j = 1; j <= k; j++){
                if(p % j == 0)
                {
                    a[1] = j;
                    a[2] = p/a[1];
                    //printf("%lld %lld %lld\n", a[0], a[1], a[2]);
                    Min = min(Min,(a[0]+1)*(a[1]+2)*(a[2]+2));
                    Min = min(Min,(a[1]+1)*(a[0]+2)*(a[2]+2));
                    Min = min(Min,(a[2]+1)*(a[1]+2)*(a[0]+2));
                    Max = max(Max,(a[0]+1)*(a[1]+2)*(a[2]+2));
                    Max = max(Max,(a[1]+1)*(a[0]+2)*(a[2]+2));
                    Max = max(Max,(a[2]+1)*(a[1]+2)*(a[0]+2));
                }
            }
        }
    }
    printf("%lld %lld\n", Min - n, Max - n);
    return 0;
}