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