首页 > 试题广场 >

马戏团

[编程题]马戏团
  • 热度指数：12756 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
搜狐员工小王最近利用假期在外地旅游，在某个小镇碰到一个马戏团表演，精彩的表演结束后发现团长正和大伙在帐篷前激烈讨论，小王打听了下了解到， 马戏团正打算出一个新节目“最高罗汉塔”，即马戏团员叠罗汉表演。考虑到安全因素，要求叠罗汉过程中，站在某个人肩上的人应该既比自己矮又比自己瘦，或相等。 团长想要本次节目中的罗汉塔叠的最高，由于人数众多，正在头疼如何安排人员的问题。小王觉得这个问题很简单，于是统计了参与最高罗汉塔表演的所有团员的身高体重，并且很快找到叠最高罗汉塔的人员序列。 现在你手上也拿到了这样一份身高体重表，请找出可以叠出的最高罗汉塔的高度，这份表中马戏团员依次编号为1到N。

输入描述:
首先一个正整数N，表示人员个数。 
之后N行，每行三个数，分别对应马戏团员编号，体重和身高。


输出描述:
正整数m，表示罗汉塔的高度。
示例1

输入

6
1 65 100
2 75 80
3 80 100
4 60 95
5 82 101
6 81 70

输出

4
算法知识视频讲解
开通博客
头像 laingdc
发表于 2023-09-26 15:45:45
#include <algorithm> #include <iostream> #include <vector> #include <algorithm> using namespace std; bool com_w(vector<in 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 烟花一树终化尘
发表于 2022-04-02 22:43:04
动态规划+二分查找 https://leetcode-cn.com/problems/circus-tower-lcci/ 题目要求在2个维度上(即身高 + 体重)同时保持递增。 那么我们可以先将其中一个维度排好序，以保证在一个维度上保持递增（此时并非严格递增）； 之后就可以专注于处理另一个维度。（ 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 bandiaoz
发表于 2024-12-29 14:03:31
解题思路 题目要求： 马戏团员需要叠罗汉表演 上面的人必须比下面的人矮且轻（或相等） 求最大能叠多高 需要处理多组输入 解题策略： 先按体重从小到大排序（相同体重时身高高的排前面） 然后对身高求最长递增子序列 使用二分查找优化LIS算法 代码 cpp java py 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客768685351号
发表于 2022-07-31 17:00:24
#include<iostream> #include<vector> #include<algorithm> using namespace std; bool cmp(const pair<int,  展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 贪吃的迪恩顶呱呱
发表于 2024-05-01 14:17:10
题目的题意有点难以理解，参考了讨论区大佬的解读： 1.如果两人体重不一样，则上面的身高要小于等于下面的身高 2.如果两人体重一样，那么他们的身高也必须一样先按照体重降序排列，再对得到的序列按照身高求最长递减子序列 #include <algorithm> #include <ios 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 冬天起床有压力
发表于 2022-01-28 00:21:04
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public stati 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客721482427号
发表于 2022-01-21 11:24:24
这道题用动态规划的思路解决 根据题意，叠罗汉下面的人比上面的人一定满足(m[i].weight>=m[j].weight&&m[i].height>=m[j].height) 那么，我们可以先根据这个思路将数据从大到小排序，然后求它的最长递减序列 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 c风x
发表于 2022-07-10 14:09:36
代码实现： import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public&n 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划
来自：搜狐2016研发工程师编程题
难度：
61条回答 21387浏览

热门推荐

通过挑战的用户

查看代码

相关试题

马戏团

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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