题目意思:有n个参赛者,他们都需要参加两场半决赛。第一场半决赛的成绩依次是aa, ..., a,分别对应第1~第n个人的成绩。第二场则是bb, ..., b。其中这两个序列都是以递增方式排列的。需要从中找出有机会跻身于总决赛的人(标记为1)包括成绩排名前k人(对应成绩是a1,b1;a2,b2,...,ak,bk)和处在两场半决赛的总成绩处在n-2k排名的人。至于k是不确定的,只知道范围是:0 ≤ 2k ≤ n

做法:

似乎显然可以证明当k=0时所能上场的人就是确定了右边界。然后当k取最大值时也就不怎么需要从k名开外的地方选人了,两个边界一叠加,答案就出来了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 100010
using namespace std;
int a[maxn],b[maxn],w[maxn],q[maxn],n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i],&b[i]);
    int i,j,z;
    i=j=z=1;
    while(z<=n){
        if(a[i]<=b[j]){
            q[i]=1;
            i++;z++;
        }
        else {
            w[j]=1;
            j++;z++;
        }
    }
    for(int i=1;i<=n/2;i++)printf("1");
    for(int i=n/2+1;i<=n;i++)printf("%d",q[i]);
    puts("");
    for(int i=1;i<=n/2;i++)printf("1");
    for(int i=n/2+1;i<=n;i++)printf("%d",w[i]);
    puts("");
    return 0;
}
01-05 18:37