team2012-E1-mysol-0012

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
/* 解题报告 //

虽然比赛时没看懂题目，但大概知道是输入一个 n，再输入 n 对数
按照输入的第一个数排序，对第二个数求最长上升子序列
如果 LIS 的长度大于等于 0.5 * n，则输出 LIS 的长度，否则输出 -1

// By 猛犸也钻地 @ 2012.07.21 */
}}}

{{{
#include <cstdio>
#include <algorithm>
using namespace std;

typedef pair<int,int> PII;

PII a[100000];
int h[100001];

int main(){
    int n;
    while(scanf("%d",&n)==1){
        for(int i=0;i<n;i++)
            scanf("%d%d",&a[i].first,&a[i].second);
        sort(a,a+n);
        fill(h,h+n,12345678);
        int ans=h[0]=0;
        for(int i=0;i<n;i++){
            int x=lower_bound(h,h+n,a[i].second)-h;
            h[x]=min(h[x],a[i].second);
            ans=max(ans,x);
        }
        if(ans<n/2) ans=-1;
        printf("%d\n",ans);
    }
}
}}}

/* 解题报告 //
虽然比赛时没看懂题目，但大概知道是输入一个 n，再输入 n 对数
按照输入的第一个数排序，对第二个数求最长上升子序列
如果 LIS 的长度大于等于 0.5 * n，则输出 LIS 的长度，否则输出 -1
// By 猛犸也钻地 @ 2012.07.21 */

#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
PII a[100000];
int h[100001];
int main(){
    int n;
    while(scanf("%d",&n)==1){
        for(int i=0;i<n;i++)
            scanf("%d%d",&a[i].first,&a[i].second);
        sort(a,a+n);
        fill(h,h+n,12345678);
        int ans=h[0]=0;
        for(int i=0;i<n;i++){
            int x=lower_bound(h,h+n,a[i].second)-h;
            h[x]=min(h[x],a[i].second);
            ans=max(ans,x);
        }
        if(ans<n/2) ans=-1;
        printf("%d\n",ans);
    }
}