问题：假设积木的宽和高均一致，仅长度不同
输入：第一行为积木数量N[1,30]
第二行是N个整数，表示各积木的长度[1,100]
输出：最多可叠成多少层等长的积木墙
例1：
输入：
5
2 3 5 4 1
输出：
3
说明：2和3做第一层，5做第二层，4和1做第三层；最多可叠成3层长度为5的积木墙。
例2：
输入：
3
1 2 4
输出：
1
说明：1/2/4三块积木叠成1层长为7的积木墙。
#include <math.h>
#include <string.h>
//冒泡排序
void bubbleArr(int arr[],int len)
{
for (int i = 0; i < len - 1; i++)
{
for (int j = 0; j < len - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
//计算整数的所有因子
void calcYZ(int sum,int *yz,int &num)
{
int i=0;
num = 0;
for(i=1;i<sqrt((double)sum);i++)
{
if(sum%i==0)
{
yz[num++] = i;
yz[num++] = sum/i;
}
}
}
int main()
{
int n,i,j,a,sum=0;
printf("请输入数字个数：");
scanf("%d",&n);
int *p = new int[n];
printf("请输入%d个数字：",n);
for(i=0;i<n;i++)
{
scanf("%d",&p[i]);
sum += p[i];
}
//计算所有因子
int yz[1000] = {0};
int num = 0;
calcYZ(sum,yz,num);
bubbleArr(yz,num); //对因子进行冒泡排序
for(i=0;i<num;i++) //对每个因子进行遍历检查
{
int k = yz[i]; //每层的数值
int m = sum/k; //层数
if(m>n) //如果层数比输入数字数量还多，显然不可能成立
continue;
int *q = new int[m]; //当前每层已经填入的数值，不能超过k
memset(q,0,m*sizeof(int));
for(j=0;j<n;j++) //遍历每个数字，加入到可以填入的层中
{
for(a=0;a<m;a++) //遍历所有的层， 检查是否有合适的层可以加入这个数值
{
if(q[a] == k) //如果该层值已经是k，则不可以加入，继续检索
continue;
if(q[a] < k && (q[a] + p[j]) <=k) //如果层值小于看且加入新值后不溢出，将数值加入该层
{
q[a] += p[j];
break;
}
}
}
for(a=0;a<m;a++) //检查是否所有层的值是否都等于k，是则当前层次即为最优层次
{
if(q[a] != k)
{
break;
}
}
delete []q;
if(a==m) //满足条件
{
printf("最多的积木墙层数为：%d\n",m);
break;
}
}
delete []p;
return 0;
}那我很想问一下，如果输入5，以及2,,3,5,4,2，那么应该是几层墙？你举得例子有些特殊，必须要每一层都完全一样长吗？
/* 考试第3题：积木叠最高的墙：划分k个相等的子集 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int n;
int src[30]={0};
int used[30]={0};
int k[30]={0};
int klen=0;
int flag=0;
int cmp(const void*a, const void*b)
{
return *(int*)b - *(int*)a;
}
/* 分组数目；每组目标和；当前和 */
void dfs(int k,int sum,int nowsum)
{
if(k==1){ //最后一组不用计算
flag=1;
return;
}
if(sum==nowsum){
dfs(k-1,sum,0); //精妙之处在于，找到一组，之前的used就不再回溯了
return;
}
if(sum<nowsum){ //启动回溯
return;
}
int i;
for(i=0;i<n;i++){
if(used[i]==0){
used[i]=1;
nowsum+=src[i];
dfs(k,sum,nowsum);
nowsum-=src[i];
used[i]=0;
}
}
}
int main()
{
scanf("%d",&n);
int i;
int sum=0;
int max=0;
for(i=0;i<n;i++){
scanf("%d",&src[i]);
sum+=src[i];
max=max>src[i]?max:src[i];
}
for(i=max;i<sum;i++){
if(sum%i==0){
k[klen++]=sum/i; //k为组数(墙高)，且递减
}
}
qsort(src,n,sizeof(int),cmp); //输入排序：递减
for(i=0;i<klen;i++){
memset(used,0,sizeof(used));
dfs(k[i],sum/k[i],0);
if(flag==1) break;
}
if(flag==1) printf("%d\n",k[i]);
else printf("1\n");
return 0;
}
您好，我是有问必答小助手，您的问题已经有小伙伴解答了，您看下是否解决，可以追评进行沟通哦~
如果有您比较满意的答案 / 帮您提供解决思路的答案，可以点击【采纳】按钮，给回答的小伙伴一些鼓励哦～～
ps:问答VIP仅需29元，即可享受5次/月 有问必答服务，了解详情>>>https://vip.csdn.net/askvip?utm_source=1146287632