题目描述
给定一个宽度为 width 的仓库，要求将 n 个箱子按之字形（Zigzag）方式摆放。每个箱子的宽度都是 1，箱子必须摆放在仓库的同一层上，且摆放过程中不能重叠。
之字形摆放的定义是：箱子交替地向左和向右对齐。即第1行从左对齐，第2行从右对齐，第3行再次从左对齐，以此类推。
需要输出按之字形摆放箱子后，每一层的最大高度。
输入
- 第一行包含两个整数 n 和 width，分别表示箱子的数量和仓库的宽度。
- 第二行包含 n 个整数，表示每个箱子的高度。
输出
- 输出一个整数数组，表示每一层的最大高度。
示例
输入
6 4
2 3 4 1 2 3
输出
[4 3 3]
解释
仓库宽度为4，6个箱子按之字形摆放如下：
2 3 4 1
2
3
每一层的最大高度分别是：4、3、3。
思路
- 计算层数：由于箱子是按之字形摆放，我们可以计算出所需的层数。层数可以通过 ceil(n / width) 计算得到，其中 ceil 表示向上取整。
- 记录每层的最大高度：使用一个数组来记录每一层的最大高度。
- 遍历箱子：按序遍历每个箱子，计算其在第几层以及是向左还是向右对齐。
- 更新当前层的最大高度：根据箱子的当前位置和高度，更新对应层的最大高度。
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)))
