用c++完成以下题目:蒜头君要和花椰妹结婚了,他要盖一幢新房子。已知建材市场有 n 种长方体砖块,每种砖块的长宽高分别为 x,y,z。蒜头君很有钱,每种砖块都可以买无限块。他想把他的房子盖得尽可能的高,但必须满足上面的砖块的长和宽要 严格小于 下面的。每种砖块可以任意旋转,也就是说长宽高可以互换。比如底面是 4×2 不能放在 1×3 下面,但旋转成 2×4 就能放下。现在蒜头君求你帮忙算出最多能把房子盖的多高。
时间: 2023-06-01 16:02:55 浏览: 296
思路:
我们可以把每种砖块旋转成长宽高从小到大的状态,然后按照长、宽、高的顺序进行排序。接着,我们可以采用贪心的策略,每次选择长和宽都小于当前砖块的最大高度的砖块,并更新该砖块的最大高度。最后,我们将所有砖块的最大高度相加即可得到最大高度。
具体实现:
我们可以将每种砖块旋转后的三种状态存储在一个结构体中,然后根据长、宽、高的顺序进行排序。接着,我们定义一个数组 $max\_height$,表示当前砖块的最大高度。我们遍历每种砖块,对于每种砖块,我们在已经放置的砖块中找到长和宽都小于当前砖块的最大高度的砖块,并更新该砖块的最大高度。最后,我们将所有砖块的最大高度相加即可得到最大高度。
代码实现:
相关问题
用c++的代码完成以下题目:蒜头君要和花椰妹结婚了,他要盖一幢新房子。已知建材市场有 n 种长方体砖块,每种砖块的长宽高分别为 x,y,z。蒜头君很有钱,每种砖块都可以买无限块。他想把他的房子盖得尽可能的高,但必须满足上面的砖块的长和宽要 严格小于 下面的。每种砖块可以任意旋转,也就是说长宽高可以互换。比如底面是 4×2 不能放在 1×3 下面,但旋转成 2×4 就能放下。现在蒜头君求你帮忙算出最多能把房子盖的多高。
思路:
首先,我们需要对每种砖块进行旋转,使得长宽高按从小到大的顺序排列,即 $x \leq y \leq z$。
然后,我们可以对所有砖块按照底面积从大到小排序,依次从大到小地考虑每一块砖能否放在当前的高度上。具体地,我们可以用一个二维数组 $dp[i][j]$ 表示前 $i$ 块砖中,底面积最大为 $j$ 的情况下的最大高度。对于第 $i$ 块砖,我们可以将其放在当前高度上,也可以不放。如果放,那么当前高度就是 $dp[i-1][j-\text{底面积}] + z$;如果不放,那么当前高度就是 $dp[i-1][j]$。最终的答案就是 $dp[n][\text{房间底面积}]$。
代码实现如下:
在新年的一年中,蒜头君拿到了新年第一题,花椰妹告诉蒜头君三个数字:n, m, f其中 n, f 为奇数,m 为 2 的幂,蒜头君需要求解最小的正整数 x,满足 x^n \% m = f。 请你帮蒜头君找到满足条件最小正整数 x,数据保证一定有解。 输入格式 输入共一行,三个正整数 n, m, f含义如上所述。 输出格式 输出共一行,一个正整数 x,表示满足条件的最小正整数。 C++代码
这是一道求模意义下的次方的问题。由于m是2的幂,所以我们可以使用快速幂算法来求x^n % m = f的最小正整数x。可以通过将x^n拆分成x^(n/2) * x^(n/2)来递归求解,直到n=1时直接返回x。同时在每次递归时用(x^(n/2) * x^(n/2)) % m来更新x,最后输出x即可。
阅读全文