粉丝47获赞159



今天我们要刷的题目是 c 加加的俄罗斯方块。首先把经典的俄罗斯方块简化一下,方块就有顺序地从屏幕顶端掉落至底部,当碰到障碍物或底部时停下, 同时变成新的障碍物。游戏规则规定,只能在方块下落停止前决定下落时的横向位置,使这个方块变成障碍物后的高度最低。 且如果有几种横向位置使这个方块变成障碍物后高度最低时,取最左边的横向位置下落。 接下来看输入第一行的第一个参数表示方块的数量,而第一行的第二个参数表示 屏幕的宽度,那么后边的每一行就代表即将下落的方块边长。接下来我们来完成这道题的代码编辑。首先我们来写框架 好,接下来处理输入,定义两个变量来保存方块的数量和屏幕的宽度。 那么接下来我们要从键盘获取输入的两个参数 好,获取完两个参数之后,我们知道屏幕的宽度,因此可以定一个一维数值来保存放置方块后的最低高度。 呃,因为我们输入的屏幕宽度是动态变化的,所以这里我们要定一个 vector 宽度为 w, 然后 vector 里边的每一个数都抽象为零。好,接下来我们来处理每一个方块。 处理 n 个方块啊,所以我们这里要循环 n 次。在循环内部,我们可以定一个临时变量 t 啊,用来保存当前方块的边长。 接下来我们获取每一个方块的边长啊。当然为了我们的程序效率更高,可以把定义的临时变量放在循环的外面, 那每一次循环我们能够获取到一个方块的边长,知道边长之后,我们要计算最佳位置, 计算可以放置方块的最佳位置,所以最佳位置啊,就是要高度最低。 接下来我们来用一个 for 循环。 好,这里为什么要小于等于 w 减 t 啊?因为我们的方块它能够放的位置要由屏幕的宽度来决定,不能越界。 好,接下来在循环中 我们要计算当前方块落下后到高度。 好,这里为什么要小于 t 加 t? 原因是当我们放置的方块在其他方块的上面时,我们方块的所有位置所占的位置高度都要统一啊,所以这里我们要计算最高的高度哈。 另一个变量存储当前的高度, 在循环内部我们加上一个判断,如果当前的高度小于放置之后的高度,那么我们当前的高度就要等于放置之后的高度。 那么当我们的 for 循环完成之后啊,完成之后就能够找到。当 for 循环循环完了,我们就能知道当前方块落下之后 高度是多少。接下来我们就要记录最佳位置, 那么最佳位置我们可以在循环的外面定义一个变量, int best p 输出为零,最佳位置。 当然题目要求要高度最低啊,所以这里我们还要再加上一个计算,如果当前的高度小于 啊,之前已经落下方块的最低高度, 那么这个时候最低高度我们要进行更新, 然后倍加位置也要记录下来。好,最佳位置就是我们要寻找的接 哎,当然如果我们要用到这个变量,那么前面我们就要对它进行定义 好,这个变量用来记录当前 最低。 好了,那么计算完最佳位置之后,我们就要让方块落下。 怎么样让方块落下?哎,就是把 每一个位置的高度都给它更新为最低高度就行, a m 等于最低的高度啊。复制好,最后呢,我们处理完 n 个方块, 就输出最高的位置就行了。那最高的位置我们用打擂台算法, 如果最大值小于 ai, 那 么最大值就要复制为 ai。 好, 当然我们最大值应该是要初设化为数值中的第一个值啊,所以在循环的位置让它从 从一开始就行了啊,就行了,最快我们就输出最大值就行了。好,接下来我们来定义 四十四行,有一个警告, 好,这里我们给它定义成五符号的 长整型。好,再定义 没问题。接下来测试运行,把题目中的测试输入复制下来, 发现输出和题目的样例输出不一致,所以接下来我们来寻找原因。首先循环 n 次来处理 n 个方块没问题,然后接下来 计算可以放置方块的最佳位置,使得高度最低小于等于 w 减 t 没问题。再往下看,计算当前方块落下后的高度, 当前高度小于放置之后的高度,没问题啊,没问题。然后这里记录最佳位置,如果当前的高度小于最小高度。好,那么这里我们来看一下, 因为最小的高度始终为零,而当前的高度的话肯定是大于零,所以这个条件就是一直都不满足,不能进入我们的判断,所以导致最终的输出结果为零。那么这里我们可以加上一个判断,如果 最小高度等于零,就是处理第一次的情况啊,特殊情况,那么我们让最小高度等于当前的高度就行了啊,这只是第一块方块。 好,那么加上这句话应该就没有问题了。接下来我们再来测试 好输出结果为四,我们来提交 好测试全部通过。好,那么这道题的答题思路和代码我们就写到这里。好,下次再见。