有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。
示例：
输入：height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110]
输出：6
解释：从上往下数，叠罗汉最多能叠 6 层：(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)
思路:
先按照身高降序按照体重升序排序，然后再对体重做最长下降子序列。
因为数据范围是10000所以n^2的算法不行，需要用栈+二分的方法做。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
struct node{
int height;
int weight;
};
static bool cmp(const node &a, const node &b){
if(a.height!=b.height) return a.height>b.height;
return a.weight<b.weight;
}
int bestSeqAtIndex(vector<int>& height, vector<int>& weight) {
int n = height.size();
if(n==0) return 0;
vector<node> arr;
for(int i=0;i<n;i++){
node tmp;
tmp.height = height[i];
tmp.weight = weight[i];
arr.push_back(tmp);
}
sort(arr.begin(), arr.end(), cmp);
//for(int i=0;i<n;i++) cout<<arr[i].height<<" "<<arr[i].weight<<endl;
vector<int> tmp(n, -1);
int cnt = 0;
tmp[0] = arr[0].weight;
cnt ++;
for(int i=1;i<n;i++){
int w = arr[i].weight;
if(w<tmp[cnt-1]){
tmp[cnt++] = w;
}else{
int l,r,mid;
l = 0;
r = cnt-1;
while(l<r){
mid = (l+r)/2;
if(tmp[mid]>w) l = mid+1;
else r = mid;
}
if(l>=0&&l<cnt&&tmp[l]<w) tmp[l] = w;
}
//for(int j=0;j<cnt;j++) cout<<tmp[j]<<" ";
//cout<<endl;
}
return cnt;