luogu#P9015. [USACO23JAN] Moo Route S

[USACO23JAN] Moo Route S

题目描述

Farmer Nhoj dropped Bessie in the middle of nowhere! At time t=0t=0, Bessie is located at x=0x=0 on an infinite number line. She frantically searches for an exit by moving left or right by 11 unit each second. However, there actually is no exit and after TT seconds, Bessie is back at x=0x=0, tired and resigned.

Farmer Nhoj tries to track Bessie but only knows how many times Bessie crosses x=0.5,1.5,2.5,,(N1).5x=0.5,1.5,2.5, \cdots ,(N−1).5, given by an array $A_0,A_1, \cdots ,A_{N−1} (1 \le N \le 10^5, 1 \le A_i \le 10^6, \sum A_i \le 10^6)$. Bessie never reaches x>Nx>N nor x<0x<0.

In particular, Bessie's route can be represented by a string of T=i=0N1AiT= \sum\limits_{i=0}^{N-1}A_i LLs and RRs where the ii-th character represents the direction Bessie moves in during the ith second. The number of direction changes is defined as the number of occurrences of LRLRs plus the number of occurrences of RLRLs.

Please help Farmer Nhoj find any route Bessie could have taken that is consistent with A and minimizes the number of direction changes. It is guaranteed that there is at least one valid route.

输入格式

The first line contains NN. The second line contains A0,A1,,AN1A_0,A_1,\cdots ,A_{N−1}.

输出格式

Output a string SS of length T=i=0N1AiT=\sum\limits_{i=0}^{N-1}A_i where SiS_i is L or R, indicating the direction Bessie travels in during second ii. If there are multiple routes minimizing the number of direction changes, output any.

题目大意

奶牛贝西开始在一条数轴上原点的位置,每次会向左或向右移动一个单位长度,最后回到了原点。

给定贝西经过 0.5,1.5,,(N1)+0.50.5,1.5,\ldots,(N-1)+0.5 的次数(用数组 AA 表示,AiA_i 表示经过 i+0.5i+0.5 的次数)。

请构造出一条可能的移动路径(由 L\texttt{L}R\texttt{R} 构成,表示向左 / 向右走),使得中途改变方向的次数尽量少

题目保证有解,若有多解,输出任意一组解即可。

翻译自

https://www.luogu.com.cn/user/556366

2
2 4
RRLRLL
3
2 4 4
RRRLLRRLLL

提示

Explanation for Sample 1

There is only 11 valid route, corresponding to the route $0 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 0$. Since this is the only possible route, it also has the minimum number of direction changes.

Explanation for Sample 2

There are 33 possible routes:

RRLRRLRLLL
RRRLRLLRLL
RRRLLRRLLL

The first two routes have 55 direction changes, while the last one has only 33. Thus the last route is the only correct output.

Scoring

  • Inputs 353-5: N2N \le 2
  • Inputs 3103-10: T=A0+A1++AN15000T=A_0+A_1+ \cdots +A_{N−1} \le 5000
  • Inputs 112011-20: No additional constraints.