codeforces B. New Year Present 解题报告

题目链接：http://codeforces.com/contest/379/problem/B

题目意思：给定一个有n个钱包的序列，其中第i个钱包需要投入ai个钱币，需要编写一个程序，使得在对第i个钱包不能连续投入两次钱币（其实对这句话理解得不是很好：Due to some technical malfunctions the robot cannot follow two "put a coin" instructions in a row。希望有错的话，大家能够指出）和只有三种操作：向左移动一步，向右移动一步和向当前位置投入钱币的条件下，输出把每个钱包需要投入的钱币数都完成的步骤。

一开始我的做法就是，输入每个钱包需要投入的钱币数时，先统计为0的钱包数，这样可避免为空时还需要投入钱币的情况。接着从左到右开始扫描，遇到需要投入钱币的钱包就投入一枚，而该钱包需要投入的钱币数就减1，继续向右移动，直到到达最后一个位置。紧接着是从右向左扫描，继续相同的操作.....直到所有钱包需要投入的钱币都为0就结束。

比较复杂

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;  

 const int maxn =  + ;

 int vis[maxn], a[maxn];

 int main()

 {

     int n, i, cnt, tcnt;

     while (scanf("%d", &n) != EOF)

     {

         memset(vis, , sizeof(vis));

         cnt = ;

         for (i = ; i <= n; i++)

         {

             scanf("%d", &a[i]);

             if (a[i] == )    // 统计不需要投入钱币的钱包数

             {

                 vis[i] = ;

                 cnt++;

             }

         }

         int flag = ;       // 1: 向右移动，0：向左移动

         while (cnt < n)

         {

             tcnt = ;    // 标记当前所处的位置

             while (flag)

             {

                 if (a[tcnt] && tcnt < n)

                 {

                     printf("P");   // 投入一枚钱币

                     a[tcnt]--;     // 当前钱包需要的钱币减一枚

                 }

                 if (!a[tcnt] && !vis[tcnt])    // 当前钱包投入一枚钱币之后刚好不再需要再投入钱币

                 {

                     vis[tcnt] = ;

                     cnt++;

                 }

                 if (cnt == n)      // 所有钱包都不需要投入钱币

                     break;

                 tcnt++;

                 if (tcnt <= n)     // 向右移动

                     printf("R");

                 else

                     flag = ;    // 设为向左移动的标志

             }

             if (cnt == n)

                 break;

             tcnt = n;

             while (!flag)

             {

                 if (a[tcnt] && tcnt > )

                 {

                     printf("P");

                     a[tcnt]--;

                 }

                 if (!a[tcnt] && !vis[tcnt])

                 {

                     vis[tcnt] = ;

                     cnt++;

                 }

                 if (cnt == n)

                     break;

                 tcnt--;

                 if (tcnt >= )

                     printf("L");

                 else

                     flag = ;

             }

         }

         printf("\n");

     }

     return ;

 }

以下是参考别人的代码再写的，可谓是真正实现了“构造法”的思想啊～～～边输入边处理，内存空间也省了。

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 using namespace std;

 int main()

 {

     int n, i, j, tmp;

     while (scanf("%d", &n) != EOF)

     {

         for (i = ; i < n; i++)

         {

             scanf("%d", &tmp);

             if (i)

                 printf("R");      // 除最左边的那个位置外，其余位置都需要从当前位置向右移动一位

             for (j = ; j < tmp; j++)    // tmp为0的时候不处理
             {

                 printf("P");

                 if (i)

                     printf("LR");  // 防止右边越界，都要向左移，接着回归当前位置

                 else

                     printf("RL");  // 最左边的那个位置的特殊处理

             }

         }

         printf("\n");

     }

     return ;

 }

巴特西

codeforces B. New Year Present 解题报告

最新文章

热门文章