题目链接：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 ;
}