(200分)- 叠积木Java JS Python C题目描述有一堆长方体积木它们的宽度和高度都相同但长度不一。小橙想把这堆积木叠成一面墙墙的每层可以放一个积木也可以将两个积木拼接起来要求每层的长度相同。若必须用完这些积木叠成的墙最多为多少层输入描述输入为一行为各个积木的长度数字为正整数并由空格分隔。积木的数量和长度都不超过5000。输出描述输出一个数字为墙的最大层数如果无法按要求叠成每层长度一致的墙则输出-1。用例输入3 6 6 3输出3说明可以每层都是长度3和6的积木拼接起来这样每层的长度为9层数为2也可以其中两层直接用长度6的积木两个长度3的积木拼接为一层这样层数为3故输出3。输入1 4 2 3 6输出-1说明无法用这些积木叠成每层长度一致的墙故输出-1。题目解析本题对每层积木数量有限制最多两个最少一个。解题思路如下单积木情况只有一个积木时最大高度为1双积木情况两个等长积木时最大高度为2两个不等长积木时最大高度为1三个及以上积木的处理方法将积木数组nums按长度降序排列确定每层长度范围最小长度nums[0]最长积木最大长度nums[0]nums[1]最长次长积木遍历可能的层长(length)初始化指针L0Rnums.length-1处理单积木层 当nums[L]length时独立成层层高1L处理双积木层 计算sum nums[L]nums[R]若sumlength成层层高1LR--若sum≠lengthsumlength时nums[L]无法与其他积木成层sumlength时nums[R]无法与其他积木成层最优解策略 由于层长越小越可能获得更高层数因此从最小层长(nums[0])开始遍历找到第一个能搭建所有积木的层长即为最优解。2026.2.15在进行逻辑分析时假设nums数组已按降序排列则第一层的长度范围应为nums[0] ~ nums[0] nums[1]当nums.length 1时需要注意的是将第一层长度最大值设为nums[0] nums[1]存在冗余问题。因为当第一层长度定义为nums[0] nums[1]时数组中任意两个积木长度之和nums[i] nums[j]1 i,j nums.length必然小于nums[0] nums[1]假设积木长度不完全相同这会导致后续遍历长度范围时产生不必要的判断更优的方案是将第一层最大长度设为nums[0] nums[-1]即最大积木与最小积木之和这样可以避免上述问题。举例说明 给定降序排列的积木长度5,4,3,3,2,1若取549作为第一层长度则没有其他积木组合能达到相同长度但若取516则存在42和33这两种组合方式JS算法源码/* JavaScript Node ACM模式 控制台输入获取 */ const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout, }); rl.on(line, (line) { const nums line.split( ).map(Number); console.log(getResult(nums)); }); function getResult(nums) { const n nums.length; // 如果只有一个积木那么只能是一层高度 if (n 1) return 1; // 如果有两个积木 // 如果两个积木长度相同则最大高度为2 // 如果两个积木长度不同则最大高度为1 if (n 2) return nums[0] ! nums[1] ? 1 : 2; // 积木按长度降序 nums.sort((a, b) b - a); // 一层的最小长度即最长的积木的长度 const minLen nums[0]; // 一层的最大长度 const maxLen nums[0] nums.at(-1); // 尝试minLen和maxLen中每一个值作为一层长度 for (let len minLen; len maxLen; len) { // 对应一层长度限制下的最大高度 let height 0; // 通过l,r指针去选择组成一层的一个或两个积木 // l指针指向最大长度的积木 let l 0; // r指针指向最小长度的积木 let r n - 1; // 如果最大长度的积木可以独立一层则lheight while (l n nums[l] len) { l; height; } // 如果 l,r积木无法组成一层 // 假设nums[l] nums[r] length则必然nums[l] nums[r-1] length // 因为nums已降序nums[r-1] nums[r]即必然l积木无法和其他积木组成一层 // 假设nums[l] nums[r] length则必然nums[l1] nums[r] length // 因为nums已降序nums[l1] nums[l]即必然r积木无法和其他积木组成一层 while (l r) { if (nums[l] nums[r] ! len) break; l; r--; height; } // 如果正常结束则必然l r否则就是异常结束 if (l r) continue; return height; } return -1; }Java算法源码import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); Integer[] nums Arrays.stream(sc.nextLine().split( )).map(Integer::parseInt).toArray(Integer[]::new); System.out.println(getResult(nums)); } public static int getResult(Integer[] nums) { int n nums.length; // 如果只有一个积木那么只能是一层高度 if (n 1) { return 1; } // 如果有两个积木 if (n 2) { // 如果两个积木长度相同则最大高度为2 // 如果两个积木长度不同则最大高度为1 return nums[0] - nums[1] ! 0 ? 1 : 2; } // 积木按长度降序 Arrays.sort(nums, (a, b) - b - a); // 一层的最小长度即最长的积木的长度 int minLen nums[0]; // 一层的最大长度 int maxLen nums[0] nums[nums.length-1]; // 尝试minLen和maxLen中每一个值作为一层长度 for (int len minLen; len maxLen; len) { // 对应一层长度限制下的最大高度 int height 0; // 通过l,r指针去选择组成一层的一个或两个积木 // l指针指向最大长度的积木 int l 0; // r指针指向最小长度的积木 int r n - 1; // 如果最大长度的积木可以独立一层则lheight while (l n nums[l] len) { l; height; } // 如果 l,r积木无法组成一层 // 假设nums[l] nums[r] length则必然nums[l] nums[r-1] length // 因为nums已降序nums[r-1] nums[r]即必然l积木无法和其他积木组成一层 // 假设nums[l] nums[r] length则必然nums[l1] nums[r] length // 因为nums已降序nums[l1] nums[l]即必然r积木无法和其他积木组成一层 while (l r) { if (nums[l] nums[r] ! len) break; l; r--; height; } // 如果正常结束则必然l r否则就是异常结束 if (l r) continue; return height; } return -1; } }Python算法源码# 输入获取 nums list(map(int, input().split())) # 算法入口 def getResult(): # 如果只有一个积木那么只能是一层高度 if len(nums) 1: return 1 # 如果有两个积木 if len(nums) 2: # 如果两个积木长度相同则最大高度为2 # 如果两个积木长度不同则最大高度为1 return 1 if nums[0] ! nums[1] else 2 # 积木按长度降序 nums.sort(reverseTrue) # 一层的最小长度即最长的积木的长度 minLen nums[0] # 一层的最大长度 maxLen nums[0] nums[-1] # 尝试minLen和maxLen中每一个值作为一层长度 for length in range(minLen, maxLen 1): # 对应一层长度限制下的最大高度 height 0 # 通过l,r指针去选择组成一层的一个或两个积木 # l指针指向最大长度的积木 l 0 # r指针指向最小长度的积木 r len(nums) - 1 # 如果最大长度的积木可以独立一层则lheight while l len(nums) and nums[l] length: l 1 height 1 while l r: # 如果 l,r积木无法组成一层 # 假设nums[l] nums[r] length则必然nums[l] nums[r-1] length因为nums已降序nums[r-1] nums[r]即必然l积木无法和其他积木组成一层 # 假设nums[l] nums[r] length则必然nums[l1] nums[r] length因为nums已降序nums[l1] nums[l]即必然r积木无法和其他积木组成一层 if nums[l] nums[r] ! length: break else: l 1 r - 1 height 1 # 如果正常结束则必然l r否则就是异常结束 if l r: continue return height return -1 # 算法调用 print(getResult())C算法源码#include stdio.h #include stdlib.h #define MAX_SIZE 5000 int getResult(); int cmp(const void *a, const void *b); int nums[MAX_SIZE]; int nums_size 0; int main() { while (scanf(%d, nums[nums_size])) { if (getchar() ! ) break; } printf(%d\n, getResult()); return 0; } int getResult() { // 如果只有一个积木那么只能是一层高度 if (nums_size 1) { return 1; } // 如果有两个积木 if (nums_size 2) { // 如果两个积木长度相同则最大高度为2 // 如果两个积木长度不同则最大高度为1 return nums[0] ! nums[1] ? 1 : 2; } // 积木按长度降序 qsort(nums, nums_size, sizeof(int), cmp); // 一层的最小长度即最长的积木的长度 int minLen nums[0]; // 一层的最大长度即最长的两个积木的长度之和 int maxLen nums[0] nums[nums_size - 1]; // 尝试minLen和maxLen中每一个值作为一层长度 for (int len minLen; len maxLen; len) { // 对应一层长度限制下的最大高度 int height 0; // 通过l,r指针去选择组成一层的一个或两个积木 // l指针指向最大长度的积木 int l 0; // r指针指向最小长度的积木 int r nums_size - 1; // 如果最大长度的积木可以独立一层则lheight while (l nums_size nums[l] len) { l; height; } while (l r) { // 如果 l,r积木无法组成一层 // 假设nums[l] nums[r] length则必然nums[l] nums[r-1] length因为nums已降序nums[r-1] nums[r]即必然l积木无法和其他积木组成一层 // 假设nums[l] nums[r] length则必然nums[l1] nums[r] length因为nums已降序nums[l1] nums[l]即必然r积木无法和其他积木组成一层 if (nums[l] nums[r] ! len) break; l; r--; height; } // 如果正常结束则必然l r否则就是异常结束 if (l r) continue; return height; } return -1; } int cmp(const void *a, const void *b) { return (*(int *) b) - (*(int *) a); }