C++ APCS實作題 2021/1 4 : 飛黃騰達

經典的 LIS(最長遞增子序列)

但把 lower_bound() 改成 upper_bound() 就會過了。 (這點我也想了一下)

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

pair<int,int> pt[200005];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>pt[i].first>>pt[i].second;
    }
    sort(pt,pt+n);
    vector<int> v;
    for(int i=0;i<n;i++){
        auto a=upper_bound(v.begin(),v.end(),pt[i].second);
        if(a==v.end()) v.push_back(pt[i].second);
        else *a=pt[i].second;
    }
    cout<<v.size();
    return 0;
}