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的标记来处理的。

 #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 ;

 }

巴特西

codeforces B. Semifinals 解题报告

最新文章

热门文章