题解 | #信封嵌套问题#

//本题需要用到最长递增子序列这一算法原型,不会的话请自行学习
#include<iostream>
#include<algorithm>
using namespace std;
struct envelope{
    int lenth;//信封的长度
    int wild;//信封的宽度
};
bool compartor(envelope a,envelope b);//比较器
int main(){
    int n;
    cin>>n;
    envelope arr[n];
    for(int i=0;i<n;i++){
        int lenth,wild;
        cin>>lenth>>wild;
        //将这个二维数组封装为一个结构体类型的一维数组，方便排序
        arr[i].lenth=lenth;
        arr[i].wild=wild;
    }
    //封装完成后进行排序，排序规则为按长度从小到大长度相同的按宽度从大到小排序
    sort(arr,arr+n,compartor);//调用sort的重载函数
    //排完序后就不用看长度了，这时候只需要求arr数组关于宽度的最长递增子序列即可
    //下面就是直接套用求数组最长递增子序列的算法原型
    int ends[n];
    int right=0;
    ends[0]=arr[0].wild;
    for(int i=1;i<n;i++){
        //用二分法查找ends数组中最左边大于等于arr[i].wild的位置
        int l=0,r=right;
        while(l<=r){
            int mid=(l+r)/2;
            if(ends[mid]>=arr[i].wild){
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        right=l>right?l:right;//更新right
        ends[l]=arr[i].wild;
    }
    cout<<right+1<<endl;
    return 0;
}
bool compartor(envelope a,envelope b){
    if(a.lenth>b.lenth)
        return false;
    else if(a.lenth==b.lenth){//长度相同时按宽度从大到小排序
        if(a.wild>b.wild)
            return true;
        else return false;
    }
    else return true;
}