刷题笔记合集🔗

叠积木

问题描述

有一堆长方体积木，它们的宽度和高度都相同，但长度不一。

小橙想把这堆积木叠成一面墙，墙的每层可以放一个积木，也可以将两个积木拼接起来，要求每层的长度相同。

若必须用完这些积木，叠成的墙最多为多少层？

输入格式

输入为一行，为各个积木的长度，数字为正整数，并由空格分隔。积木的数量和长度都不超过5000。

输出格式

输出一个数字，为墙的最大层数，如果无法按要求叠成每层长度一致的墙，则输出-1。

样例输入

3 6 6 3

1 4 2 3 6

样例输出

3

-1

数据范围

题解

这道题主要考察贪心算法和双指针技巧。我们需要找到一种合适的每层长度，使得所有积木都能被用完，并且墙的层数最多。

首先分析一下简单情况：

1. 如果只有一个积木，那么最大高度是1
2. 如果有两个积木：
   • 两个积木长度相同时，最大高度为2
   • 两个积木长度不同时，最大高度为1

对于更一般的情况，我们需要找到一个合适的每层长度。如果能找到这样的长度，让所有积木恰好组成多层且每层长度相同，那么就能得到最大的墙高。

解题思路如下：

1. 首先将所有积木按长度降序排列
2. 确定每层可能的长度范围：最小长度为最长积木的长度，最大长度为最长积木与最短积木的和
3. 在这个范围内尝试每一个可能的长度值，看是否能将所有积木都使用完

对于每个尝试的长度值，我们用双指针的方法来检查是否所有积木都能被分配：

1. 左指针L指向当前最长的未使用积木
2. 右指针R指向当前最短的未使用积木
3. 检查当前最长的积木是否等于尝试的层长度：
   • 如果是，则这个积木可以单独成层，左指针右移
4. 否则，尝试将左指针和右指针的积木组合起来：
   • 如果恰好等于尝试的层长度，则两个积木可以组合成一层，左指针右移，右指针左移
   • 否则，这个尝试的长度值不可行

如果能够成功分配所有积木，则返回对应的层数；如果尝试所有可能的层长度都无法成功分配所有积木，则返回-1。

这个算法的时间复杂度为O(n log n + n * L)，其中n是积木数量，L是可能的层长度范围大小，最坏情况下为O(n^2)。但在实际应用中，由于积木长度通常有限，算法的效率是可以接受的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 输入获取
blocks = list(map(int, input().split()))

def max_layers(blocks):
    n = len(blocks)
    
    # 处理特殊情况
    if n == 1:
        return 1
    if n == 2:
        # 两个积木长度相同，可以各自一层
        if blocks[0] == blocks[1]:
            return 2
        # 长度不同，最多只能一层
        else:
            return 1
    
    # 将积木按长度降序排序
    blocks.sort(reverse=True)
    
    # 确定尝试的层长度范围
    min_len = blocks[0]  # 最小长度为最长积木的长度
    max_len = blocks[0] + blocks[-1]  # 最大长度为最长积木与最短积木的和
    
    # 尝试每一个可能的层长度
    for layer_len in range(min_len, max_len + 1):
        # 创建积木列表的副本进行模拟
        temp = blocks.copy()
        layers = 0
        
        # 使用双指针法分配积木
        while temp:
            l, r = 0, len(temp) - 1
            
            # 如果最长的积木等于层长度，可以单独成一层
            if temp[l] == layer_len:
                temp.pop(l)
                layers += 1
                continue
            
            # 尝试组合左右指针的积木
            if l < r and temp[l] + temp[r] == layer_len:
                temp.pop(r)  # 先移除右侧的，索引不会变化
                temp.pop(l)
                layers += 1
                continue
            
            # 无法分配积木，这个层长度不可行
            break
        
        # 如果所有积木都被分配了，返回层数
        if not temp:
            return layers
    
    # 无法找到合适的层长度
    return -1

# 输出结果
print(max_layers(blocks))

• Cpp

#include <bits/stdc++.h>
using namespace std;

int maxLayers(vector<int>& blocks) {
    int n = blocks.size();
    
    // 处理特殊情况
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        // 两个积木长度相同，可以各自一层
        if (blocks[0] == blocks[1]) {
            return 2;
        }
        // 长度不同，最多只能一层
        else {
            return 1;
        }
    }
    
    // 将积木按长度降序排序
    sort(blocks.begin(), blocks.end(), greater<int>());
    
    // 确定尝试的层长度范围
    int minLen = blocks[0];  // 最小长度为最长积木的长度
    int maxLen = blocks[0] + blocks[n-1];  // 最大长度为最长与最短积木的和
    
    // 尝试每一个可能的层长度
    for (int