(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

三个及以上积木的处理方法：

1. 将积木数组nums按长度降序排列
2. 确定每层长度范围：
   • 最小长度：nums[0]（最长积木）
   • 最大长度：nums[0]+nums[1]（最长+次长积木）
3. 遍历可能的层长(length)：
   • 初始化指针L=0，R=nums.length-1
   • 处理单积木层： 当nums[L]==length时，独立成层，层高+1，L++
   • 处理双积木层： 计算sum = nums[L]+nums[R]
     • 若sum==length：成层，层高+1，L++，R--
     • 若sum≠length：
       • sum>length时：nums[L]无法与其他积木成层
       • sum<length时：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

• 若取5+4=9作为第一层长度，则没有其他积木组合能达到相同长度
• 但若取5+1=6，则存在4+2和3+3这两种组合方式

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;

    // 如果最大长度的积木，可以独立一层，则l++，height++
    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[l+1] + nums[r] < length，
    // 因为nums已降序，nums[l+1] <= 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;

      // 如果最大长度的积木，可以独立一层，则l++，height++
      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[l+1] + nums[r] < length，
      // 因为nums已降序，nums[l+1] <= 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(reverse=True)

    # 一层的最小长度，即最长的积木的长度
    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

        # 如果最大长度的积木，可以独立一层，则l++，height++
        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[l+1] + nums[r] < length，因为nums已降序，nums[l+1] <= 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;

        // 如果最大长度的积木，可以独立一层，则l++，height++
        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[l+1] + nums[r] < length，因为nums已降序，nums[l+1] <= 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);
}