C++ 解法, 执行用时: 4ms, 内存消耗: 416KB, 提交时间: 2022-07-08

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010;
int endsArr[N];

struct Letter {
    int height, width;
    bool operator < (const Letter& L) const {
        return height != L.height? height < L.height: width > L.width;
    }
} letters[N];

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        int h, w;
        scanf("%d%d", &h, &w);
        letters[i] = {h, w};
    }
    if(n == 1) {
        cout << 1 << endl;
        return 0;
    }
    sort(letters, letters + n);
//     for(int i = 0; i < n; i++) cout << letters[i].height << " " << letters[i].width << endl;
    endsArr[0] = letters[0].width;
    int size = 0;
    for(int i = 1; i < n; i++) {
        int index = lower_bound(endsArr, endsArr + size + 1, letters[i].width) - endsArr;
        if(index == size + 1) {
            size++;
        }
        endsArr[index] = letters[i].width;
    }
    printf("%d\n", size + 1);
    return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 432KB, 提交时间: 2022-08-06

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200010;
int endsArr[N];
struct Letter{
    int height,width;
    bool operator < (const Letter &L) const{
        return height!=L.height?height<L.height:width>L.width;
    }
}letters[N];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int h,w;
        scanf("%d%d",&h,&w);
        letters[i]={h,w};
    }
    if(n==1)
    {
        cout<<1<<endl;
        return 0;
    }
    sort(letters,letters+n);
    endsArr[0]=letters[0].width;
    int  size=0;
    for(int i=1;i<n;i++)
    {
        int index=lower_bound(endsArr, endsArr+size+1,letters[i].width)-endsArr;
        if(index==size+1)
        {
            size++;
        }
        endsArr[index]=letters[i].width;
    }
    printf("%d\n",size+1);
    return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 464KB, 提交时间: 2022-03-11

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Env
{
    int __length;
    int __width;
//     Env() : __length(0), __width(0) {}
};

struct Node
{
    int __val;
    int __idx;
    Node(int val, int idx) : __val(val), __idx(idx) {}
};

class treeVec
{
public:
    treeVec(int n)
    {
        __tVec = vector<int>(n, 0);
    }
    
    int lowestbit(int x)
    {
        return x & (-x);
    }
    
    void modify(int x, int y)
    {
        while (x < __tVec.size())
        {
            __tVec[x] = max(__tVec[x], y);
            x += lowestbit(x);
        }
    }
    
    int query(int x)
    {
        int ret = 0;
        while (x)
        {
            ret = max(ret, __tVec[x]);
            x -= lowestbit(x);
        }
        
        return ret;
    }
    
public:
    vector<int> __tVec;
    vector<Node> __tNodeVec;
};

class solution
{
public:
//     int getResult(vector<int> &nums)
//     {
//         int n = unique(nums.begin(), nums.end()) - nums.begin();
//         treeVec mtreeVec(n);
//         for (int i = 1; i < n; i++)
//         {
//             mtreeVec.__tNodeVec.emplace_back(Node(nums[i], i));
//         }
        
//         sort(mtreeVec.__tNodeVec.begin(), mtreeVec.__tNodeVec.end(), [](Node a, Node b){
//             return a.__val == b.__val ? a.__idx < b.__idx : a.__val < b.__val;
//         });
        
//         int ret = 0;
//         for (auto [val, idx] : mtreeVec.__tNodeVec)
//         {
//             int tMax = mtreeVec.query(idx);
//             mtreeVec.modify(idx, ++tMax);
//             ret = max(ret, tMax);
//         }
        
//         return ret;
//     }
    
    int getResult(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> dp(n);
        dp[0] = nums[0];
        int len = 1;
         
        for (int i = 1; i < n; i++)
        {
            if (nums[i] > dp[len - 1])
            {
                dp[len++] = nums[i];
            }
            else
            {
                int j = lower_bound(dp.begin(), dp.begin() + len, nums[i]) - dp.begin();
                dp[j] = nums[i];
            }
        }
         
        return len;
    }
};

int main()
{
    int n;
    solution mSolution;
    
    cin >> n;
    cin.get();
    vector<Env> envs(n);
    for (int i = 0; i < n; i++)
    {
        cin >> envs[i].__length >> envs[i].__width;
        cin.get();
    }
    sort(envs.begin(), envs.end(), [](Env a, Env b)
         {
             return a.__length == b.__length ? a.__width > b.__width : a.__length < b.__length;
         });
//     vector<int> nums(n + 1, 0);
//     for (int i = 1; i <= n; i++)
//     {
//         nums[i] = envs[i - 1].__width;
//     }
    
    vector<int> nums(n);
    
    for (int i = 0; i < n; i++)
    {
        nums[i] = envs[i].__width;
    }
    
    cout << mSolution.getResult(nums) << endl;
    
    return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 484KB, 提交时间: 2022-07-21

#include <bits/stdc++.h> // C++万能头文件
using namespace std;
static const auto io_sync_off = [](){ // lambda表达式
    std::ios::sync_with_stdio(false); // 解除与scanf()等函数的同步
    std::cin.tie(nullptr); // 解除cin和cout的绑定
    return nullptr;
}();

using pii = pair<int, int>;
int main() {
    int n;
    cin >> n;
    vector<pii> v;
    while (n--) {
        int a, b;
        cin >> a >> b;
        v.emplace_back(a, b);
    }
    sort(v.begin(), v.end(), [](auto& a, auto& b){
       if (a.first == b.first) return a.second > b.second;
        return a.first < b.first;
    }); // 排序后若宽度维大于之前信封，长度维一定大于之间信封
    vector<int> dp; // 求宽度维最长递增子序列的最小长度
    for (auto& [a, b] : v) {
        if (dp.empty() || dp.back() < b)
            dp.push_back(b);
        else
            *lower_bound(dp.begin(), dp.end(), b) = b;
    }
    cout << dp.size() << "\n";
    return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 524KB, 提交时间: 2022-03-14

#include <cstdio>
#include <vector>
#include <algorithm>
// 最长递增子序列的长度
int maxsubarray(const std::vector<std::vector<int>> &letters) {
    int pies = 0;
    int size = letters.size();
    std::vector<int> pokers(size);
    for (int i = 0; i < size; ++i) {
        int left = 0, right = pies, mid;
        while (left < right) {
            mid = left + ((right - left) >> 1);
            if (pokers[mid] < letters[i][1]) left = mid + 1;
            else right = mid;
        }
        if (left == pies) ++pies;
        pokers[left] = letters[i][1];
    }
    return pies;
}
int main() {
    int n;
    scanf("%d", &n);
    std::vector<std::vector<int>> letters(n, std::vector<int>(2));
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%d %d", &letters[i][0], &letters[i][1]);
    }
    std::sort(letters.begin(), letters.end(), [](const std::vector<int> &a, const std::vector<int> &b)
              { if (a[0] != b[0]) return a[0] < b[0]; else return a[1] > b[1]; });
    int st = letters[0][0], ed = letters[0][1];
    // 求最长递增子序列的长度
    printf("%d\n", maxsubarray(letters));
    return 0;
}