首页 > 试题广场 >

信封嵌套问题

[编程题]信封嵌套问题
  • 热度指数：2369 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给n个信封的长度和宽度。如果信封A的长和宽都小于信封B，那么信封A可以放到信封B里，请求出信封最多可以嵌套多少层。

输入描述:
输出包含多行，第一行包括一个整数，代表信封的个数n。接下来n行，每行两个整数l_i和w_i，代表信封的长度和宽度。


输出描述:
输出包括一行，代表信封最多嵌套多少层。
示例1

输入

9
3 4
2 3
4 5
1 3
2 2
3 6
1 2
3 2
2 4

输出

4

说明

从里到外分别是{1，2}，{2，3}，{3，4}，{4，5}。
示例2

输入

2
1 4
4 1

输出

1

备注:
时间复杂度，空间复杂度。
算法知识视频讲解
开通博客
头像 总之就是非常可爱
发表于 2022-02-14 19:47:36
//本题需要用到最长递增子序列这一算法原型,不会的话请自行学习 #include<iostream> #include<algorithm> using namespace std; struct envelope{     int lenth;//信封的 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 开挂了的菜鸡很想奋斗
发表于 2023-09-03 19:02:27
本题可通过巧妙的处理将问题转化为最长递增子序列问题，将先信封的长边（li)由小到大排序，在同等长边（li）的情况下按宽边（wi）由大到小排序。之后将排序后的宽边（wi）按最长递增子序列问题处理。 #include <cstdio> #include <vector> #inc 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 快支棱起来的椰子很愤怒
发表于 2022-01-12 16:54:05
n = int(input()) envlope = [] for _ in range(n): envlope.append(list(map(int, input().split()))) envlope.sort(key = lambda x: (x[0], -x[1])) res = 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划 排序
上传者：小小
难度：
11条回答 5603浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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