简化版俄罗斯方块：最小化障碍物高度

简化版俄罗斯方块：最小化障碍物高度

题目描述

把经典的俄罗斯方块简化一下：方块有顺序地从屏幕顶端掉下到底部，当碰到障碍物或底部时将停下，同时变成新的障碍物。游戏规则规定，只能在方块下落停止前决定下落时的横向位置，使这个方块变成障碍物后，高度尽量低，且如果有几种横向位置，使这个方块变成障碍物后高度最低，取最左边的横向位置下落。

输入描述

第一行仅包含两个正整数，分别表示方块数n和屏幕宽度w，两数间用一个空格分隔。

接下来的n行，每行仅有一个正整数，表示各个方块的边长a。

输出描述

输出一个整数，表示最后障碍物最高点的高度

示例

输入

3 5
2
3
1

输出

5

代码实现

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, w;
    cin >> n >> w;

    vector<int> blocks(n);
    for (int i = 0; i < n; i++) {
        cin >> blocks[i];
    }

    vector<int> heights(w, 0); // 记录每个位置的最大高度

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

        // 遍历每个横向位置，找到使得方块下落后高度最低的位置
        for (int j = 0; j < w; j++) {
            int maxHeight = 0;
            for (int k = j; k < j + blocks[i]; k++) {
                maxHeight = max(maxHeight, heights[k]);
            }
            if (maxHeight < minHeight) {
                minHeight = maxHeight;
                leftPos = j;
            }
        }

        // 更新每个位置的高度
        for (int j = leftPos; j < leftPos + blocks[i]; j++) {
            heights[j] = minHeight + blocks[i];
        }
    }

    // 找到最高的高度
    int maxHeight = 0;
    for (int i = 0; i < w; i++) {
        maxHeight = max(maxHeight, heights[i]);
    }

    cout << maxHeight << endl;

    return 0;
}

代码解析

该代码使用了两个vector，blocks存储了每个方块的边长，heights记录了每个位置的最大高度。首先，根据输入初始化blocks，然后遍历每个方块，找到使得方块下落后高度最低的位置，并更新heights。最后，遍历heights找到最高的高度，并输出结果。