首页 > 试题广场 >

搭积木

[编程题]搭积木
  • 热度指数：18781 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小明有一袋子长方形的积木，如果一个积木A的长和宽都不大于另外一个积木B的长和宽，则积木A可以搭在积木B的上面。好奇的小明特别想知道这一袋子积木最多可以搭多少层，你能帮他想想办法吗？
定义每一个长方形的长 L 和宽 W ，袋子里面长方形的个数为 n 。
假如袋子里共有5个积木分别为 (2, 2), (2, 4), (3, 3), (2, 5), (4, 5), 则不难判断这些积木最多可以搭成4层, 因为(2, 2) < (2, 4) < (2, 5) < (4, 5)。

数据范围：长方形个数满足 ，

输入描述:
第一行为积木的总个数 N

之后一共有N行，分别对应于每一个积木的宽W和长L


输出描述:
输出总共可以搭的层数
示例1

输入

5
2 2
2 4
3 3
2 5
4 5

输出

4
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2020-06-04 14:41:57
精华题解 题目难度：三星考察点：排序、最长不下降子序列（O(nlogn)） 方法1：排序、动态规划 分析：根据题意，我们可以首先按照长度（或者是宽度）其中之一进行排序，那么我们接下来就只需要想办法将宽度搭积木的层数变得最多就可以了，将其转化为了最长不下降子序列（因为序列中是可以有相等的情况）的问题，我们就可 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 laglangyue
发表于 2020-05-22 01:00:45
我太难了，折磨了三个小时 import java.lang.reflect.Array; import java.security.Key; import java.util.*; public class Main { public static int upBound(int[] d 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 cchangcs
发表于 2019-09-04 18:55:55
题目描述： 链接：https://www.nowcoder.com/questionTerminal/55371b74b2f243e3820e57ee4c7b5504 来源：牛客网 小明有一袋子长方形的积木，如果一个积木A的长和宽都不大于另外一个积木B的长和宽，则积木A可以搭在 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 岩之痕
发表于 2019-08-18 14:31:25
题目转化 首先将题目数据按照(W, L)排序。如果(W1, L1) < (W2, L2)，再加上题目给的W <= L条件，则(W2, L2)只能被放在(W1, L1)下面。如果(W1, L1) = (W2, L2)，两个积木完全相等，先后顺序没有限制，在不影响答案正确性的情况下，可以自己 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 维拉小王子
发表于 2020-03-30 18:34:13
题解 最长非降子序列问题描述： 给若干个数，输出这些数能组成的最长非降子序列的长度。如2,4,6,3,4,5,6的最长非降子序列为2,3,4,5,6。所以最长非降子序列长度为5。最长非降子序列问题经典解法--动态规划DP--时间复杂度O(nlogn) input的数 能组成的非降子序列 非 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 iOS工程师 安卓工程师 快手 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 游戏研发工程师 排序 动态规划 2019 Java工程师
上传者：小小
难度：
48条回答 18035浏览

热门推荐

通过挑战的用户

查看代码

相关试题

搭积木

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号