描述把经典的俄罗斯方块简化一下:方块有顺序地从屏幕顶端掉下到底部当碰到障碍物或底部时将停下同时变成新的障碍物。游戏规则规定只能在方块下落停止前决定下落时的横向位置使这个方块变成障碍物后高度尽量低且如果有几种横向位置使这个方块变成障碍物后高度最低取最左边的横向位置下落。捕获PNG输入描述第一行仅包含两个正整数分别表示方块数n和屏幕宽度w两数间用一个空格分隔。接下来的n行每行仅有一个正整数表示各个方块
题目要求实现一个简化版的俄罗斯方块游戏。方块按顺序从屏幕顶端掉落到底部,碰到障碍物或底部停止,并变成新的障碍物。玩家只能在方块下落停止前决定方块的横向位置,使得方块下落后的高度尽量低,并且如果有多种横向位置都能使得方块下落后的高度最低,选择最左边的位置。
输入的第一行包含两个正整数n和w,分别表示方块数和屏幕宽度。接下来的n行每行包含一个正整数a,表示各个方块的边长。
输出一个整数,表示最后障碍物的最高点的高度。
以下是一种可能的C++实现代码:
#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找到最高的高度,并输出结果
原文地址: http://www.cveoy.top/t/topic/iPg6 著作权归作者所有。请勿转载和采集!