codeforces B. Semifinals 解题报告

题目链接：http://codeforces.com/problemset/problem/378/B

题目意思：有n个参赛者，他们都需要参加两场半决赛。第一场半决赛的成绩依次是a₁, a₂, ..., a_n，分别对应第1～第n个人的成绩。第二场则是b₁, b₂, ..., b_n。其中这两个序列都是以递增方式排列的。需要从中找出有机会跻身于总决赛的人（标记为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("
");
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("
");
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
0
");
70             else
71                 printf("0
1
");
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 }