题解 | #信封嵌套问题#

本题可通过巧妙的处理将问题转化为最长递增子序列问题，将先信封的长边（li)由小到大排序，在同等长边（li）的情况下按宽边（wi）由大到小排序。之后将排序后的宽边（wi）按最长递增子序列问题处理。

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

int main() {
    int vecSize;
    scanf("%d", &vecSize);
    vector<vector<int>> veci = vector(vecSize, vector<int>(2));
    for(int i = 0; i < vecSize; ++i)
    {
        int l;
        int w;
        scanf("%d%d", &l, &w);
        veci[i][0] = l;
        veci[i][1] = w;
    }
    sort(veci.begin(), veci.end(), [](vector<int> &a, vector<int> &b){return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];});     //长边按从小到大排序，宽边从大到小排序
    vector<int> load(vecSize);
    for(int i = 0; i < vecSize; ++i)
    load[i] = veci[i][1];
    vector<int> pile(vecSize);
    int piles = 0;
    for(int i = 0; i < vecSize; ++i)
    {
        int left = 0;
        int right = piles;
        int pocker = load[i];
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(pile[mid] > pocker)
            right = mid;
            else if(pile[mid] < pocker)
            left = mid + 1;
            else
            right = mid;
        }
        if(left == piles) ++piles;
        pile[left] = pocker;
    }
    printf("%d", piles);
    return 0;
}