友好城市

传送门

这道题就像洋葱 一层一层剖开以后 其实本质就是lis

所谓友好城市

其实就是左边一个点和右边一个点之间有连线

那么问题就转化成了去掉多少个连边使得所有的边没有交点

我们对任意一边的点的坐标进行排序以后 求出另外一边的lis即可

//友好城市 
#include<bits/stdc++.h>
using namespace std;
const int mxn=2e5+5;
struct canal{
    int x,y;
}a[mxn];
bool cmp(canal a,canal b){
    return a.x<b.x;
}
int lis[mxn];
int main(){
    int n;
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].x,&a[i].y);
    }
    sort(a+1,a+n+1,cmp);
    lis[++ans]=a[1].y;
    for(int i=2;i<=n;i++){
        if(a[i].y>lis[ans]){
            lis[++ans]=a[i].y;
        }else{
            lis[upper_bound(lis+1,lis+ans+1,a[i].y)-lis]=a[i].y;
        }
    }
    cout<<ans;
    return 0;
}