prow2012-A3-0012

从 Trac 迁移的文章

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

原文章内容如下：

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

a,b  a作为下标，b作为数值，最长不下降子序列即可。

{{{

#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <math.h>
using namespace std;
const int MAXN = 100100;
#define _cp(a,b) (!((a)>(b)))

template <class elemType>
int subseq(int n, const elemType * a) {
    int b[MAXN + 1], i, l, r, m, ret = 0;
    for (i = 0; i < n; b[l] = i++, ret += (l> ret)) {
        for (m = ((l = 1) + (r = ret)) >> 1; l <= r; m = (l + r) >> 1) {
            if (_cp(a[b[m]], a[i])) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
    }
    return ret;
}
int num[MAXN];
int main(){
    int N,i,a,b;
    while(scanf("%d",&N)!=EOF){
        for (i=0;i<N;i++)
        {
            scanf("%d%d",&a,&b);
            a--,b--;
            num[a] = b;
        }
        int ans = subseq(N,num);
        if (ans*2>=N) printf("%d\n",ans);
        else printf("-1\n");
    }
}

}}}

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

a,b a作为下标，b作为数值，最长不下降子序列即可。

#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <math.h>
using namespace std;
const int MAXN = 100100;
#define _cp(a,b) (!((a)>(b)))
template <class elemType>
int subseq(int n, const elemType * a) {
    int b[MAXN + 1], i, l, r, m, ret = 0;
    for (i = 0; i < n; b[l] = i++, ret += (l> ret)) {
        for (m = ((l = 1) + (r = ret)) >> 1; l <= r; m = (l + r) >> 1) {
            if (_cp(a[b[m]], a[i])) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
    }
    return ret;
}
int num[MAXN];
int main(){
    int N,i,a,b;
    while(scanf("%d",&N)!=EOF){
        for (i=0;i<N;i++)
        {
            scanf("%d%d",&a,&b);
            a--,b--;
            num[a] = b;
        }
        int ans = subseq(N,num);
        if (ans*2>=N) printf("%d\n",ans);
        else printf("-1\n");
    }
}