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就结束。

     比较复杂

     

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 using namespace std;  
 6 
 7 const int maxn = 300 + 10;
 8 int vis[maxn], a[maxn];
 9 
10 int main()
11 {
12     int n, i, cnt, tcnt;
13     while (scanf("%d", &n) != EOF)
14     {
15         memset(vis, 0, sizeof(vis));
16         cnt = 0;
17         for (i = 1; i <= n; i++)
18         {
19             scanf("%d", &a[i]);
20             if (a[i] == 0)    // 统计不需要投入钱币的钱包数
21             {
22                 vis[i] = 1;
23                 cnt++;
24             }
25         }
26         int flag = 1;       // 1: 向右移动,0:向左移动
27         while (cnt < n)  
28         {
29             tcnt = 1;    // 标记当前所处的位置
30             while (flag)   
31             {
32                 if (a[tcnt] && tcnt < n)
33                 {
34                     printf("P");   // 投入一枚钱币
35                     a[tcnt]--;     // 当前钱包需要的钱币减一枚
36                 }
37                 if (!a[tcnt] && !vis[tcnt])    // 当前钱包投入一枚钱币之后刚好不再需要再投入钱币
38                 {
39                     vis[tcnt] = 1;
40                     cnt++;   
41                 }
42                 if (cnt == n)      // 所有钱包都不需要投入钱币
43                     break;
44                 tcnt++;
45                 if (tcnt <= n)     // 向右移动
46                     printf("R");
47                 else
48                     flag = 0;    // 设为向左移动的标志
49             } 
50             if (cnt == n)
51                 break;
52             tcnt = n;
53             while (!flag)
54             {
55                 if (a[tcnt] && tcnt > 1)
56                 {
57                     printf("P");
58                     a[tcnt]--;
59                 }
60                 if (!a[tcnt] && !vis[tcnt])
61                 {
62                     vis[tcnt] = 1;
63                     cnt++;
64                 }
65                 if (cnt == n)
66                     break;   
67                 tcnt--;
68                 if (tcnt >= 1)   
69                     printf("L");
70                 else
71                     flag = 1;
72             }    
73         } 
74         printf("\n");
75     }
76     return 0;
77 }

 

 

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

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int n, i, j, tmp;
 9     while (scanf("%d", &n) != EOF)
10     {
11         for (i = 0; i < n; i++)
12         {
13             scanf("%d", &tmp);
14             if (i)
15                 printf("R");      // 除最左边的那个位置外,其余位置都需要从当前位置向右移动一位
16             for (j = 0; j < tmp; j++)    // tmp为0的时候不处理
17 { 18 printf("P"); 19 if (i) 20 printf("LR"); // 防止右边越界,都要向左移,接着回归当前位置 21 else 22 printf("RL"); // 最左边的那个位置的特殊处理 23 } 24 } 25 printf("\n"); 26 } 27 return 0; 28 }

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。