Task 1.纸壳子(box.pas/box.c/box.cpp)
【题目描述】
Mcx是一个有轻度洁癖的小朋友。有一天,当他沉溺于数学卷子难以自拔的时候,恍惚间想起在自己当初学习概率的时候准备的一堆橡皮还杂乱地堆在自习室里。这显然是他无法容忍的。于是他决定做一个体积为V(V=abc)的纸盒子,以便能整齐的摆放它们。为了简单起见,这个纸盒子的长、宽、高均为正整数。当然了,Mcx是一个以勤俭闻名的小朋友,因此他想知道,这个纸盒子的表面积(S=2ab+2ac+2bc)的最小值是多少呢?
【题目输入】
仅一行,为一个正整数V,表示纸盒子的体积。
【题目输出】
仅一行,为一个正整数S,表示纸盒子的最小表面积。
【样例输入1】
17
【样例输出1】
70
【样例输入2】
146
【样例输出2】
442
【样例解释】
对于体积为17的盒子只有一种制作方法就是长1宽1高17(这里我们可以认为长,宽,高是等价的),于是它的最小表面积就是2*1*17+2*1*17+2*1*1 = 70
【数据范围】
30%数据满足V<=1000
100%数据满足V<=10^9
分析:
首先!这是一道!数学题!!数学题就要有数学题的样子//这道要比其他数论妖艳贱货题好多了。
这道题其实没有什么高深的解法。但是想一想其实就是枚举。枚举a,枚举b之后c就自然就出来了。
而刚才的方法,瞎基本搞,小数据应该可以拿分。
第一种优化就是枚举a的时候只需要枚举a<=pow(v , 1.0/3 );只枚举前面的。而b就用枚举b<=sqrt(v/a);
c直接就可以求出。当然还要对它进行是不是整数的判断。
第二种优化就是枚举a的时候。对是否枚举b的剪枝判断。我们知道因为在枚举a的时候。v与a就是定值。表面积公式就是2*(ab+bc+ac)就改变成了2*(v/a+a*(b+c)) 而表面积的最小值,就转变成了(b+c)的最小值。我们又知道v/a==bc 那么 bc 也是定值 所以当b==c的时候是理论最小值。所以我们如果求出的理论最小值都要比我们枚举出来的a的答案大。那我们就没有必要再去枚举b。
为什么b*c为一定的时候 当b==c 时 (b+c)最小呢?
这里特别感谢数竞大爷的讲解:

贴出代码:

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
freopen("box.in","r",stdin);
freopen("box.out","w",stdout);
int v;
long long int ans=1000000000000000LL,bmj;
scanf("%d",&v);
for(int a=v;a>=1;--a)
{
if((v/a)*a!=v)continue;
int kk=sqrt(v/a);
bmj=(long long int)(v/a+a*2*kk);
if(bmj<=ans||a==v){
for(int b=a;b<=a+kk;++b){
int c=v/a/b;
if(c*a*b!=v)continue;
ans=min(ans,(long long int)a*b+(long long int)b*c+(long long int)a*c);
}
}
}
printf("%I64d",2*ans);
fclose(stdin);
fclose(stdout);
return 0;
}

最新文章

  1. 项目游戏开发日记 No.0x000002
  2. gcd推导
  3. (转)Mybatis高级映射、动态SQL及获得自增主键
  4. Partitioning
  5. iOS中的imageIO与image解码
  6. client denied by server configuration
  7. vi find和grep
  8. C# Setup package Uninstaller
  9. [置顶] 和孩子们一起学Python编程
  10. STL系列
  11. 异常:Injection of autowired dependencies failed; nested exception is java.lang.IllegalArgumentException
  12. mac 开发新户攻略-brew
  13. Nim积解法小结
  14. 性能测试进阶指南——基础篇之磁盘IO
  15. Maven中阿里云私服配置
  16. NLog类库使用探索——详解配置
  17. nodejs写入json文件,格式化输出json的方法
  18. SQL邮件服务(解决各种疑难杂症)+案例 + 使用SQLserver 邮件系统发送SQL代理作业执行警告
  19. MFC Activex 开发、ocx打包成cab、部署、测试、自动升级
  20. SQL Fundamentals: Using Single-Row Functions to Customize Output使用单行函数自定义输出

热门文章

  1. JQuery源码解析(一)
  2. Java提高篇(三六)-----Java集合细节(二):asList的缺陷
  3. zend studio 常用快捷键
  4. 用DirectX实现魔方(二)
  5. Mysql跨表更新 多表update sql语句总结
  6. NSDate NSString相互转化
  7. Windows hosts (使用方法 &amp;&amp; 不定期更新)
  8. Atitit 理解Monad attilax总结
  9. Atitit 常用比较复杂的图像滤镜 attilax大总结
  10. Atitit cnchar simp best list &#160;汉字简化方案 最简化汉字256个