题解 | #马戏团#

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Person {
    int id, weight, height;
};

// 按体重排序，体重相同时身高高的排前面
bool compare(const Person& a, const Person& b) {
    if(a.weight != b.weight) return a.weight < b.weight;
    return a.height > b.height;
}

// 二分查找第一个大于x的位置
int binarySearch(vector<int>& arr, int len, int x) {
    int left = 0, right = len - 1;
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(arr[mid] <= x) left = mid + 1;
        else right = mid - 1;
    }
    return left;
}

// 求最长递增子序列
int getLIS(vector<Person>& people) {
    if(people.empty()) return 0;
    vector<int> dp;
    dp.push_back(people[0].height);
    
    for(int i = 1; i < people.size(); i++) {
        if(people[i].height >= dp.back()) {
            dp.push_back(people[i].height);
        } else {
            int pos = binarySearch(dp, dp.size(), people[i].height);
            dp[pos] = people[i].height;
        }
    }
    return dp.size();
}

int main() {
    int n;
    while(cin >> n) {  // 处理多组输入
        vector<Person> people(n);
        
        // 读取输入
        for(int i = 0; i < n; i++) {
            cin >> people[i].id >> people[i].weight >> people[i].height;
        }
        
        // 按体重排序
        sort(people.begin(), people.end(), compare);
        
        // 计算最大高度
        cout << getLIS(people) << endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    static class Person {
        int id, weight, height;
        Person(int id, int weight, int height) {
            this.id = id;
            this.weight = weight;
            this.height = height;
        }
    }
    
    // 二分查找第一个大于x的位置
    static int binarySearch(int[] arr, int len, int x) {
        int left = 0, right = len - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(arr[mid] <= x) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }
    
    // 求最长递增子序列
    static int getLIS(Person[] people) {
        if(people.length == 0) return 0;
        int[] dp = new int[people.length];
        int len = 0;
        dp[len++] = people[0].height;
        
        for(int i = 1; i < people.length; i++) {
            if(people[i].height >= dp[len-1]) {
                dp[len++] = people[i].height;
            } else {
                int pos = binarySearch(dp, len, people[i].height);
                dp[pos] = people[i].height;
            }
        }
        return len;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {  // 处理多组输入
            int n = sc.nextInt();
            Person[] people = new Person[n];
            
            // 读取输入
            for(int i = 0; i < n; i++) {
                people[i] = new Person(sc.nextInt(), sc.nextInt(), sc.nextInt());
            }
            
            // 按体重排序
            Arrays.sort(people, (a, b) -> {
                if(a.weight != b.weight) return a.weight - b.weight;
                return b.height - a.height;
            });
            
            // 计算最大高度
            System.out.println(getLIS(people));
        }
    }
}

class Person:
    def __init__(self, id, weight, height):
        self.id = id
        self.weight = weight
        self.height = height

def binary_search(arr, length, x):
    left, right = 0, length - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] <= x:
            left = mid + 1
        else:
            right = mid - 1
    return left

def get_lis(people):
    if not people:
        return 0
    dp = [people[0].height]
    
    for i in range(1, len(people)):
        if people[i].height >= dp[-1]:
            dp.append(people[i].height)
        else:
            pos = binary_search(dp, len(dp), people[i].height)
            dp[pos] = people[i].height
    return len(dp)

# 处理多组输入
while True:
    try:
        n = int(input())
        people = []
        
        # 读取输入
        for _ in range(n):
            id, weight, height = map(int, input().split())
            people.append(Person(id, weight, height))
        
        # 按体重排序，体重相同时身高高的排前面
        people.sort(key=lambda x: (x.weight, -x.height))
        
        # 计算最大高度
        print(get_lis(people))
    except EOFError:
        break