首页 > 代码库 > careercup-排序和查找 11.7
careercup-排序和查找 11.7
11.7 有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。处于实际和美观的考虑，在上面的人要比下面的人矮一点、轻一点。已知马戏团每个人的高度和重量，请编写代码计算叠罗汉最多能叠几个人。
如果要保持相对顺序不变，那么不能直接排序。
C++实现代码：
#include<iostream>#include<vector>using namespace std;struct people{ int weight; int lenght; people(int w,int l):weight(w),lenght(l){}};bool isValid(vector<people> &path,people &p){ if(path.empty()) return true; people tmp=path.back(); return p.lenght<tmp.lenght&&p.weight<tmp.weight;}void helper(vector<people> &pp,int start,int &longSequence,vector<people> &path){ if(start==pp.size()) { if(longSequence<path.size()) longSequence=path.size(); return; } int i; for(i=start;i<pp.size();i++) { //该条件可以不成立，因此不能进入递归 if(isValid(path,pp[i])) { path.push_back(pp[i]); helper(pp,i+1,longSequence,path); path.pop_back(); } }}int getIncreasingSequence(vector<people> &pp){ int longSequence=0; vector<people> path; helper(pp,0,longSequence,path); return longSequence;}int main(){ vector<people> p={people(1,1),people(2,2),people(3,3),people(4,4)}; cout<<getIncreasingSequence(p)<<endl;}
careercup-排序和查找 11.7
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。