2012-A3-0012

从 Trac 迁移的文章

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

原文章内容如下：

题意：双方各N人，甲方每个人都有一个必然能战胜的人，甲乙双方方必须按编号从小到大,问甲方能否战胜一半及以上的场次..

排序后求个最长上升子序列

{{{
#include<cstdio>
#include<algorithm>
using namespace std;
typedef size_t tp;
#define F first
#define S second
pair<tp,tp> p[102400];
tp q[102400];
int main(){
    for(tp n,m;~scanf("%u",&n);m*2<n?puts("-1"):printf("%u\n",m)){
        for(tp i=0;i<n;++i)
            scanf("%u%u",&p[i].F,&p[i].S);
        sort(p,p+n);
        q[m=0]=0;
        for(tp i=0;i<n;++i)
            if(p[i].S>q[m])q[++m]=p[i].S;
            else *upper_bound(q,q+m,p[i].S) = p[i].S;
    }
}
}}}

题意：双方各N人，甲方每个人都有一个必然能战胜的人，甲乙双方方必须按编号从小到大,问甲方能否战胜一半及以上的场次..

排序后求个最长上升子序列

#include<cstdio>
#include<algorithm>
using namespace std;
typedef size_t tp;
#define F first
#define S second
pair<tp,tp> p[102400];
tp q[102400];
int main(){
    for(tp n,m;~scanf("%u",&n);m*2<n?puts("-1"):printf("%u\n",m)){
        for(tp i=0;i<n;++i)
            scanf("%u%u",&p[i].F,&p[i].S);
        sort(p,p+n);
        q[m=0]=0;
        for(tp i=0;i<n;++i)
            if(p[i].S>q[m])q[++m]=p[i].S;
            else *upper_bound(q,q+m,p[i].S) = p[i].S;
    }
}