Snow Footprints CodeForces - 298A 的题解
Problem
有一条笔直的雪路，被划分为n个区块。这些区块从左到右依次编号为1到n。如果有人从第i个区块移动到第(i + 1)个区块，他会在第i个区块留下一个右脚印。同理，若从第i个区块移动到第(i - 1)个区块，则会在第i个区块留下左脚印。如果第i个区块上已有脚印，新脚印会覆盖旧的。
最初雪路上没有任何脚印。随后北极熊爱丽丝从第s个区块出发，经过一系列移动后抵达第t个区块。已知爱丽丝始终没有离开这条雪路。
现在给出爱丽丝留下的脚印描述。你的任务是通过观察脚印，找出一组可能的s, t值。
输入格式
第一行包含整数n (3 ≤ n ≤ 1000)。
第二行是雪路的描述——由n个字符组成的字符串。每个字符可能是"."（无脚印区块）、"L"（左脚印区块）或"R"（右脚印区块）。
数据保证字符串中至少有一个非"."字符。且首尾字符始终为"."。题目保证解存在。
输出格式
输出两个用空格分隔的整数——s和t的值。若有多组解，输出任意一组即可。
样例
| Inputcopy | Outputcopy |
|---|---|
9 ..RRLL... |
3 4 |
| Inputcopy | Outputcopy |
|---|---|
11 .RRRLLLLL.. |
7 5 |
提示
第一个测试样例对应题目中的图示。
标签
greedy implementation
难度
1300
Solution
简单构造
观察整个序列，一定是形如
..... + RRRRR + LLLLL + .....
的形式
手玩几组数据就可以发现这个规律
那么，我们可以这样构造
从第一个 'R' 开始往右走
在往回走到第一个 'L'
但是要注意边界
判断全是 'R' 或者 'L' 的情况，就直接从左端到右端或者右端到左端即可
另外的细节是注意终点没有脚印，注意多一少一
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
char c[N];
int main() {cin >> n;for (int i = 1; i <= n; i++) cin >> c[i];int s = -1, t = -1;for (int i = 1; i <= n; i++) if (c[i] == 'R') {s = i; break;}for (int i = 1; i <= n; i++) if (c[i] == 'L') {t = i - 1; break;}if (s == -1) {for (int i = n; i >= 1; i--) if (c[i] == 'L') {s = i; break;}}if (t == -1) {for (int i = n; i >= 1; i--) if (c[i] == 'R') {t = i + 1; break;}}cout << s << ' ' << t;return 0;
}