题目链接：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的标记来处理的。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 1e5 + 10; 8 int cnta, cnt, flag, n; 9 int a[maxn], b[maxn]; 10 11 void solve(int len, int a[], int b[]) // 始终表示a比b小 12 { 13 int i, j; 14 for (i = len, j = 1; i <= n; ) 15 { 16 if (a[i] < b[j]) 17 { 18 cnta++; 19 i++; 20 } 21 else 22 j++; 23 cnt++; 24 if (cnt == n) 25 break; 26 } 27 if (cnta == 0 && a[len] > b[len]) // 专门是处理第二组数据的情形 28 { 29 flag = 1-flag; // 剩下的n-2k个人只能都从大的那条序列里找 30 cnta = n - 2*(len-1); 31 } 32 } 33 34 void show1() 35 { 36 int i; 37 for (i = 1; i <= n/2; i++) 38 printf("1"); 39 for (i = 1; i <= cnta; i++) 40 printf("1"); 41 for (i = 1; i <= n-cnta-n/2; i++) 42 printf("0"); 43 printf("\n"); 44 } 45 46 void show2() 47 { 48 int i; 49 for (i = 1; i <= n; i++) 50 { 51 if (i <= n/2) 52 printf("1"); 53 else 54 printf("0"); 55 } 56 printf("\n"); 57 } 58 59 int main() 60 { 61 int i, k; 62 while (scanf("%d", &n) != EOF) 63 { 64 for (i = 1; i <= n; i++) 65 scanf("%d%d", &a[i], &b[i]); 66 if (n == 1) 67 { 68 if (a[1] < b[1]) 69 printf("1\n0\n"); 70 else 71 printf("0\n1\n"); 72 } 73 else 74 { 75 k = n/2 + 1; 76 cnt = n/2; 77 cnta = flag = 0; // 0: a，1：b 78 if (a[k-1] < b[k-1]) 79 solve(k, a, b); // a[k-1]前都为1 80 else 81 { 82 flag = 1-flag; 83 solve(k, b, a); 84 } 85 if (!flag) 86 { 87 show1(); 88 show2(); 89 } 90 else 91 { 92 show2(); 93 show1(); 94 } 95 } 96 } 97 return 0; 98 }