#include<stdio.h> #include<algorithm> using namespace std; struct node { int north; int south;//先定义一个结构体，里面包含了north（北岸城市）和south（南岸城市） }; node a[200005]; int n,i,d[200005],len,temp; bool cmp(node x,node y) { return x.north<y.north;//我们只需要对北岸排序求南岸的最长不下降子序列即可（可以反过来，对南岸排序求北岸的最长不下降子序列） } int main () { scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i].north); scanf("%d",&a[i].south); } sort(a+1,a+1+n,cmp);//sort结构体排序大法吼啊！ d[++len]=a[1].south;//因为最短的不下降子序列是每个数本身，所以，我们将第一个元素放进最长不下降子序列中。 for(i=2;i<=n;i++) { int dbzjrQwQ=upper_bound(d+1,d+len+1,a[i].south)-d; d[dbzjrQwQ]=a[i].south; if(dbzjrQwQ>len) { len++; } } printf("%d",len); return 0; }