【2024华为OD-E卷-100分-箱子之字形摆放】（（题目+思路+Java&C++&Python解析)

题目描述

给定一个宽度为 width 的仓库，要求将 n 个箱子按之字形（Zigzag）方式摆放。每个箱子的宽度都是 1，箱子必须摆放在仓库的同一层上，且摆放过程中不能重叠。

之字形摆放的定义是：箱子交替地向左和向右对齐。即第1行从左对齐，第2行从右对齐，第3行再次从左对齐，以此类推。

需要输出按之字形摆放箱子后，每一层的最大高度。

输入

输出

示例

输入

6 4
2 3 4 1 2 3

输出

[4 3 3]

解释

仓库宽度为4，6个箱子按之字形摆放如下：

2 3 4 1
      2
      3

每一层的最大高度分别是：4、3、3。

思路

1. 计算层数：由于箱子是按之字形摆放，我们可以计算出所需的层数。层数可以通过 ceil(n / width) 计算得到，其中 ceil 表示向上取整。
2. 记录每层的最大高度：使用一个数组来记录每一层的最大高度。
3. 遍历箱子：按序遍历每个箱子，计算其在第几层以及是向左还是向右对齐。
4. 更新当前层的最大高度：根据箱子的当前位置和高度，更新对应层的最大高度。

Java 实现

import java.util.*;

public class ZigzagBoxes {

    public static int[] getMaxHeights(int n, int width, int[] heights) {

        int layers = (int) Math.ceil((double) n / width);
        int[] maxHeights = new int[layers];

        for (int i = 0; i < n; i++) {

            int layer = i / width;
            int positionInLayer = i % width;
            boolean leftAligned = layer % 2 == 0;

            int columnIndex = leftAligned ? positionInLayer : width – 1 – positionInLayer;
            maxHeights[layer] = Math.max(maxHeights[layer], heights[i]);

            // To keep track of the effective max height at each "virtual" column position within the layer
            // (for debugging/visualization purposes, not needed for final solution)
            // This part is commented out as it's not required by the problem statement
            /*
            if (leftAligned) {

                // Left-aligned layer visualization (not needed for solution)
                System.out.print(heights[i] + " ");
            } else {

                // Right-aligned layer visualization with adjusted indexing (not needed for solution)
                System.out.print(heights[i] + " ".repeat(width – positionInLayer – 1));
                System.out.print(heights[i] + " | ");
            }
            if ((i + 1) % width == 0) System.out.println();
            */
        }

        return maxHeights;
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int width = scanner.nextInt();
        int[] heights = new int[n];
        for (int i = 0; i < n; i++) {

            heights[i] = scanner.nextInt();
        }
        int[] result = getMaxHeights(n, width, heights);
        for (int height : result) {

            System.out.print(height + " ");
        }
    }
}

C++ 实现

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

std::vector<int> getMaxHeights(int n, int width, const std::vector<int>& heights) {

    int layers = std::ceil(static_cast<double>(n) / width);
    std::vector<int> maxHeights(layers, 0);

    for (int i = 0; i < n; ++i) {

        int layer = i / width;
        int positionInLayer = i % width;
        bool leftAligned = layer % 2 == 0;

        int columnIndex = leftAligned ? positionInLayer : width – 1 – positionInLayer;
        // Note: columnIndex is used here just for logical understanding,
        // but actually we directly update the max height of the current layer
        maxHeights[layer] = std::max(maxHeights[layer], heights[i]);
    }

    return maxHeights;
}

int main() {

    int n, width;
    std::cin >> n >> width;
    std::vector<int> heights(n);
    for (int i = 0; i < n; ++i) {

        std::cin >> heights[i];
    }
    std::vector<int> result = getMaxHeights(n, width, heights);
    for (int height : result) {

        std::cout << height << " ";
    }
    return 0;
}

Python 实现

def get_max_heights(n, width, heights):
    layers = math.ceil(n / width)
    max_heights = [0] * layers

    for i in range(n):
        layer = i // width
        position_in_layer = i % width
        left_aligned = layer % 2 == 0

        column_index = position_in_layer if left_aligned else width – 1 – position_in_layer
        # Note: column_index is not used directly in final calculations,
        # but helps in understanding the logical arrangement
        max_heights[layer] = max(max_heights[layer], heights[i])

    return max_heights

import math
import sys
input = sys.stdin.read
data = input().split()

n = int(data[0])
width = int(data[1])
heights = list(map(int, data[2:n+2]))

result = get_max_heights(n, width, heights)
print(" ".join(map(str, result)))

作者：执着的小火车