用c++完成以下题目:蒜头君要和花椰妹结婚了,他要盖一幢新房子。已知建材市场有 n 种长方体砖块,每种砖块的长宽高分别为 x,y,z。蒜头君很有钱,每种砖块都可以买无限块。他想把他的房子盖得尽可能的高,但必须满足上面的砖块的长和宽要 严格小于 下面的。每种砖块可以任意旋转,也就是说长宽高可以互换。比如底面是 4×2 不能放在 1×3 下面,但旋转成 2×4 就能放下。现在蒜头君求你帮忙算出最多能把房子盖的多高。
时间: 2023-06-01 10:02:55 浏览: 287
C++编写长方体类,并求体积和表面积.
4星 · 用户满意度95%
思路:
我们可以把每种砖块旋转成长宽高从小到大的状态,然后按照长、宽、高的顺序进行排序。接着,我们可以采用贪心的策略,每次选择长和宽都小于当前砖块的最大高度的砖块,并更新该砖块的最大高度。最后,我们将所有砖块的最大高度相加即可得到最大高度。
具体实现:
我们可以将每种砖块旋转后的三种状态存储在一个结构体中,然后根据长、宽、高的顺序进行排序。接着,我们定义一个数组 $max\_height$,表示当前砖块的最大高度。我们遍历每种砖块,对于每种砖块,我们在已经放置的砖块中找到长和宽都小于当前砖块的最大高度的砖块,并更新该砖块的最大高度。最后,我们将所有砖块的最大高度相加即可得到最大高度。
代码实现:
阅读全文