Moo Route

题目描述

农夫 Nhoj 把 Bessie 丢在了荒郊野外！在时间 $t=0$ 时，Bessie 位于无限数轴上的 $x=0$。她惊慌失措地寻找出口，每秒向左或向右移动 $1$ 个单位。然而实际上并没有出口，经过 $T$ 秒后，Bessie 又回到了 $x=0$，疲惫且无奈。 农夫 Nhoj 试图追踪 Bessie，但他只知道 Bessie 穿过 $x=.5, 1.5, 2.5, \ldots, (N-1).5$ 的次数，这些次数由数组 $A_0,A_1,\dots,A_{N-1}$ 给出（$1\leq N \leq 10^5$, $1 \leq A_i \leq 10^6$, $\sum A_i\le 10^6$）。Bessie 从未到达 $x>N$，也从未到达 $x<0$。 具体来说，Bessie 的路线可以表示为一个由 $T = \sum_{i=0}^{N-1} A_i$ 个 $L$ 和 $R$ 组成的字符串，其中第 $i$ 个字符表示 Bessie 在第 $i$ 秒移动的方向。方向改变次数定义为子串 $LR$ 出现的次数加上子串 $RL$ 出现的次数。 请帮助农夫 Nhoj 找出任意一条与 $A$ 相一致、且方向改变次数最少的 Bessie 可能走过的路线。保证至少存在一条合法路线。

输入格式

第一行包含 $N$。 第二行包含 $A_0,A_1,\dots,A_{N-1}$。

输出格式

输出一个长度为 $T = \sum_{i=0}^{N-1} A_i$ 的字符串 $S$，其中 $S_i$ 为 $L$ 或 $R$，表示 Bessie 在第 $i$ 秒的移动方向。 如果有多条路线都能使方向改变次数最少，输出任意一条即可。

2
2 4

RRLRLL

3
2 4 4

RRRLLRRLLL

提示

只有 1 条合法路线，对应路径为 $0\to 1 \to 2 \to 1\to 2 \to 1\to 0$。由于这是唯一可能的路线，因此它的方向改变次数也最少。

有 3 条可能的路线： RRLRRLRLLL RRRLRLLRLL RRRLLRRLLL 前两条路线有 5 次方向改变，而最后一条只有 3 次。 因此最后一条路线是唯一正确的输出。

评分： 输入 3-5：$N\le 2$ 输入 3-10：$T = A_0 + A_1 + \cdots + A_{N-1} \leq 5000$ 输入 11-20：无额外限制。 题目鸣谢：Brandon Wang 和 Claire Zhang

标签: USACO|2023|Silver

来源

USACO|2023|Silver