本文共 1993 字，大约阅读时间需要 6 分钟。

1.积木(block)

题目描述

味味有一个A×B×C 的长方体积木，积木是有1×1×1 的小积木块组成的。我们设定这个长方体的高为A，宽为B，长为C。(为方便起见，长方体的长不一定要比宽的数值大)。

现在味味在这个长方体中的的左上角挖去了一个(A-1)×(B-2)×(C-2)的小长方体。并且告诉你被挖去长方体的体积为n，即n=(A-1)×(B-2)×(C-2)。现在问你，被挖去小长方体后，原有长方体积木中剩下的1×1×1的小积木块最少和最多分别是多少个。也就是说，在告诉你n值的前提下，求min{A×B×C-n}和max{A×B×C-n}。

输入

输入文件名为 block.in。

输入共1行，仅一个正整数n。

输出

输出文件名为 block.out。

输出共1行包含两个用空格隔开的正整数，依次表示最少剩余小积木块和最多剩余小积木块个数。

样例输入

【样例输入1】

4

【样例输入2】

7

样例输出

【样例输出1】

28 41

【样例输出2】

47 65

数据范围限制

对于20%的数据1 ≤n≤400

对于50%的数据1 ≤n≤10^6 对于100%的数据1 ≤ n≤10^9

提示

样例1说明：

4=(2-1)×(4-2)×(4-2) 最少剩余的小积木块为2×4×4-4=28（此时A，B，C值分别为2，4，4） 4=(5-1)×(3-2)×(3-2) 最多剩余的小积木块为5×3×3-4=41（此时A，B，C值分别为5，3，3）

正解

贪心算法，枚举挖出去的长方体的长a，宽b，高c 因为n=(A-1)×(B-2)×(C-2) 所以大的长方体=(a+1)x(b+2)x(c+2)（a，b，c分别是挖去的长方体的长，宽，高） 我们可以只枚举a和b，用n/a/b求出c 但是，必须 n%a=0，n/a%b=0，a乘b乘c=n 但是我们枚举a的范围是多少呢?

for(long long a=1;a*a*a<=n;a++)

因为n的长最小为1，所以是从1开始

因为a乘b乘c=n，是三个数相乘，所以循环的条件应该是a³<=n （如果a乘b乘c都>n了，那么搜下去也就没用了）

知道了a，我们再来看看b的范围

for(long long b=a;a*b*b<=n;b++)

从a开始，节省了时间

循环的条件也是三个数相乘

既然我们b从a开始，那么我们的循环内容肯定也和普通的不同

m1=min((a+1)*(b+2)*(c+2),m1);m1=min((a+2)*(b+1)*(c+2),m1);m1=min((a+2)*(b+2)*(c+1),m1);m2=max((a+1)*(b+2)*(c+2),m2);m2=max((a+2)*(b+1)*(c+2),m2);m2=max((a+2)*(b+2)*(c+1),m2);

我们每种条件都要判断一下，

a	b	c
+1	+2	+2
+2	+1	+2
+2	+2	+1

循环解决了，现在来解决输出

cout<
   
    <<' '<
   

记得要-n，因为求的是挖走后的体积

录屏链接

AC代码

#include
   
    #include
    
     using namespace std;long long n,m1,m2;int main(){   	//freopen("block.in","r",stdin);	//freopen("block.out","w",stdout);	cin>>n;	m1=2147483647;//找最小值	for(long long a=1;a*a*a<=n;a++)//循环	 if(n%a==0)//判断是否可以整除	  for(long long b=a;a*b*b<=n;b++)	   if(n/a%b==0)//判断是否可以整除	   {   	  		long long c=n/a/b;	  		if(a*b*c==n)//是否相乘为n	  		{   	   		    m1=min((a+1)*(b+2)*(c+2),m1);//3种情况				m1=min((a+2)*(b+1)*(c+2),m1);			    m1=min((a+2)*(b+2)*(c+1),m1);			    m2=max((a+1)*(b+2)*(c+2),m2);			    m2=max((a+2)*(b+1)*(c+2),m2);			    m2=max((a+2)*(b+2)*(c+1),m2);	  		}	   }	cout<
     
      <<' '<
     
    
   

下面附本次比赛的其它题目

谢谢观看

本博客制作不易，希望能点个赞再走哦（谢谢各位巨佬莅临）