题目链接:http://codeforces.com/problemset/problem/378/B
题目意思:有n个参赛者,他们都需要参加两场半决赛。第一场半决赛的成绩依次是a1, a2, ..., an,分别对应第1~第n个人的成绩。第二场则是b1, b2, ..., bn。其中这两个序列都是以递增方式排列的。需要从中找出有机会跻身于总决赛的人(标记为1)包括成绩排名前k人(对应成绩是a1,b1;a2,b2,...,ak,bk)和处在两场半决赛的总成绩处在n-2k排名的人。至于k是不确定的,只知道范围是:0 ≤ 2k ≤ n
首先可以知道k可以取的最大数是n/2(当然有可能除不尽的,即n是奇数),也就是说两场半决赛有机会晋级总决赛的人数分别至少有前n/2个。我们只需要根据条件来看两场半决赛剩余的n/2个人中还有哪些有机会可以晋级。很容易想到考虑成绩好的那个序列里挑(一),但是这个情况考虑不够周全。test 18(二)的测试数据充分证明了这点。
(一) 3 (二) 3
1 3 2 1
2 4 3 4
6 5 6 5
接着说说如何挑。先考虑第(一)组数据。从数字较小的那个序列的第k+1个数(前k个数已经确定)来与大的那个序列的第1个数开始比较:即第1列的2和第2列的3比较。由于2比3小,则把第2个人加入有机会晋级的行列(第一场半决赛),人数加一(即cnta++,cnta统计小的那个序列的后k+1符合条件的人数),直到总人数等于n。至于第(二)组数据的处理,我是根据cnta = 0和a[len] > b[len]这两个条件同时满足的情况下来处理的,表示小的那个序列的第k+1个位置的数比大的那个序列的前k+1个数都要大,于是剩下的n-2k个人只能从大的那个序列的人里找。
至于如何标识两个序列谁大谁小,我是通过flag的标记来处理的。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std; const int maxn = 1e5 + ;
int cnta, cnt, flag, n;
int a[maxn], b[maxn]; void solve(int len, int a[], int b[]) // 始终表示a比b小
{
int i, j;
for (i = len, j = ; i <= n; )
{
if (a[i] < b[j])
{
cnta++;
i++;
}
else
j++;
cnt++;
if (cnt == n)
break;
}
if (cnta == && a[len] > b[len]) // 专门是处理第二组数据的情形
{
flag = -flag; // 剩下的n-2k个人只能都从大的那条序列里找
cnta = n - *(len-);
}
} void show1()
{
int i;
for (i = ; i <= n/; i++)
printf("");
for (i = ; i <= cnta; i++)
printf("");
for (i = ; i <= n-cnta-n/; i++)
printf("");
printf("\n");
} void show2()
{
int i;
for (i = ; i <= n; i++)
{
if (i <= n/)
printf("");
else
printf("");
}
printf("\n");
} int main()
{
int i, k;
while (scanf("%d", &n) != EOF)
{
for (i = ; i <= n; i++)
scanf("%d%d", &a[i], &b[i]);
if (n == )
{
if (a[] < b[])
printf("1\n0\n");
else
printf("0\n1\n");
}
else
{
k = n/ + ;
cnt = n/;
cnta = flag = ; // 0: a,1:b
if (a[k-] < b[k-])
solve(k, a, b); // a[k-1]前都为1
else
{
flag = -flag;
solve(k, b, a);
}
if (!flag)
{
show1();
show2();
}
else
{
show2();
show1();
}
}
}
return ;
}