学步园

大意就是给俩个数列 a1 b1 .a2 b2,a3 b3.。。。讲这些相连 最多能有多少没有交叉的

把俩个样例画下机会发现只要满足 Ai < AJ && Bi < Bj  那么就不会交叉

而且给的这些只要相连没有其他规定。。那么将A  或 B 从小到大排序，这时候就会满足AI < AJ 或者Bi < Bj 的情况。

看个人习惯吧。。我是习惯定A。。。然后就在左边找最多满足BI < BJ 的情况。。就会发现是求最长上升子序列的问题。。原本打算直接俩重循环。。后来发现N = 500000..只能用nlogn的方法才能过。nlong 的方法是 用到二分。关于这个的资料文库里面很多，也很好理解，动手模拟下就可以了。

尼玛。。然后输出坑爹啊。。居然还有分s的 还有要多输出一行、WA了2次，PE2次，。。

<span style="font-size:18px;">#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int const MAXN = 500010;
int s[MAXN];
struct S{
    int l,r;
}a[MAXN];
int Binary_Search(int l,int r,int x){
    while(l <= r){
        int m =(l + r)>>1;
        if(s[m] > x) r = m - 1;
        else if(s[m] == x) return m;
        else l = m + 1;
    }
    return l;
}
bool cmp(S x,S y){
    if(x.l != y.l) return x.l < y.l;
    return x.r < y.r;
}
int main(){
    int k = 1,n;
    while(~scanf("%d",&n)){
        for(int i = 1;i <= n;i++){
            scanf("%d%d",&a[i].l,&a[i].r);
        }
        sort(a+1,a+n+1,cmp);
        s[0] = -1;
        int top = 0;
        for(int i = 1;i <= n;i++){
            if(a[i].r > s[top]) s[++top] = a[i].r;
            else{
                int m = Binary_Search(1,top,a[i].r);
                s[m] = a[i].r;
            }
        }
        printf("Case %d:\n",k++);
        if(top == 1) printf("My king, at most 1 road can be built.\n");
        else printf("My king, at most %d roads can be built.\n",top);
        printf("\n");
    }
    return 0;
}
</span>