当前位置:首页>java>在邹城学C++编程之枚举算法案例1

在邹城学C++编程之枚举算法案例1

  • 2026-08-24 11:42:51
在邹城学C++编程之枚举算法案例1
有一套积木共n个,每个积木都是一个立方体,长宽高都是1厘米.
现在要把这些积木放入一个长方体里,用牛皮纸包装起来运输,
请问,至少需要多大的牛皮纸?
输入:占一行,为一个正整数n,表示需要包装的积木数量.
输出:占一行,为包装n个积木所需要的牛皮纸的最小面积,单位为平方厘米
样例:
输入 9,输出30
输入26,输出82
说明:
当n=9时,可以包装成1×1×9/1×3×3两种大小的长方体,表面积时38和30,所以最小的表面积是30
当n=26时,可以包装成1×1×26/1×2×13两种大小的长方体,表面积时106和82,所以最小的表面积是82
数据规模与约定:
对于20%的数据,1<=n<=10
对于50%的数据,1<=n<=100
对于80%的数据,1<=n<=500
对于100%的数据,1<=n<=1000
分析:
题目的意思,是使n个积木"堆满"整个长方体,不能有空隙.
假设长方体的长宽高分别是abc,a是最短的棱,b次之,c最长,这样容易理解
枚举a的长度,从1开始,a的取值要满足a^3<=n
对a的每个取值,枚举b,b的取值从a开始,而且要满足a×b×b<=n
对每一对ab组合,如果n%(a*b)!=0,则跳过,否则c=n/(a*b),从而求出表面积.
最后取最小的表面积.
注意:
实现时,如果枚举c,则只能通过80%的数据的评测.
代码如下:
#include<bits/stdc++.h>using namespace std;intmain(){	int n;//积木个数	cin >> n; 	int a,b,c;//枚举变量	int s,mn;//表面积 最小面积	mn = 1000*1000*1000;	for(a=1;a*a*a<=n;a++){		for(b=a;a*b*b<=n;b++){			//小技巧,n%(a*b)==0,则执行循环体内语句 			// n%(a*b)!=0,则跳过循环体内语句 			if(n%(a*b))continue;			c=n/(a*b);			s=2*a*b+2*a*c+2*b*c;			if(s<mn) mn=s;		}	} 	cout << mn << endl;	return 0;}

枚举算法是最基础的算法,这个题目又是基础中的基础,少年们,连起来吧!

最新文章

随机文章