C++刷LeetCode（面试题 17.08. 马戏团人塔）【sort*】
本帖最后由 糖逗 于 2020-7-2 13:19 编辑题目描述：
有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。
示例：
输入：height = weight =
输出：6
解释：从上往下数，叠罗汉最多能叠 6 层：(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)
提示：
height.length == weight.length <= 10000
bool cmp(pair<int, int> & a, pair<int, int> &b){
if(a.first < b.first) return true;
else if(a.first == b.first) return (a.second > b.second) ? true : false;
else return false;
}
class Solution {
public:
int bestSeqAtIndex(vector<int>& height, vector<int>& weight) {
int len = height.size();
vector<pair<int, int> > temp(len);
for(int i = 0; i < len; i++){
temp.first = height;
temp.second = weight;
}
sort(temp.begin(), temp.end(), cmp);
//for(auto it : temp){
//cout << it.first << " " << it.second << endl;
//}
vector<int> dp;
for(int i = 0; i < len ; i++){
int id = lower_bound(dp.begin(), dp.end(), temp.second) - dp.begin();
cout << id << endl;
if(id == dp.size()) dp.push_back(temp.second);//该数字在dp中没有出现过
else dp = temp.second;
}
return dp.size();
}
};
注意事项：lower_bound参考链接:https://www.cnblogs.com/Tang-tangt/p/9291018.html
页:
[1]