出题人：描述把经典的俄罗斯方块简化一下：方块有顺序地从屏幕顶端掉下到底部当碰到障碍物或底部时将停下同时变成新的障碍物。游戏规则规定只能在方块下落停止前决定下落时的横向位置使这个方块变成障碍物后高度尽量低且如果有几种横向位置使这个方块变成障碍物后高度最低取最左边的横向位置下落。捕获PNG输入描述第一行仅包含两个正整数分别表示方块数n和屏幕宽度w两数间用一个空格分隔。接下来的n行每行仅有一个正整数表示

思路：根据题目描述，方块下落时，只能决定下落时的横向位置，使得方块变成障碍物后高度最低且最左边。因此，我们可以使用一个数组来表示屏幕，数组的每个元素表示对应位置的高度。

具体实现：

1. 初始化一个长度为w的数组heights，每个元素初始化为0，表示屏幕的高度。
2. 读取方块数n和屏幕宽度w。
3. 循环读取n个方块的边长a，对于每个方块，从左到右遍历每个横向位置i： a. 找到当前横向位置i下方的最低高度min_height，即从i到i+a-1的高度的最小值。 b. 将当前方块的高度加到min_height，表示方块下落后的高度。
4. 找到heights数组中的最大值，即最后障碍物的最高点的高度。

代码实现如下：

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

int main() {
    int n, w;
    std::cin >> n >> w;
    
    std::vector<int> heights(w, 0);
    
    for (int i = 0; i < n; i++) {
        int a;
        std::cin >> a;
        
        int min_height = *std::min_element(heights.begin(), heights.begin() + a);
        
        for (int j = 0; j < a; j++) {
            heights[j + min_height] += a;
        }
    }
    
    int max_height = *std::max_element(heights.begin(), heights.end());
    std::cout << max_height << std::endl;
    
    return 0;
}

复杂度分析：

• 时间复杂度：遍历n个方块，对于每个方块需要在heights数组中找到最小值，时间复杂度为O(n*w)。
• 空间复杂度：需要一个长度为w的数组来表示屏幕高度，空间复杂度为O(w)