📝 题目大意

有 $100$ 个横向排列的琴键，高桥君要依次按下 $N$ 个键，每次按键指定用左手（L）或右手（R）。演奏前可以任意放置双手（疲劳度为 $0$），手从键 $x$ 移动到键 $y$ 时疲劳度增加 $|y-x|$。求演奏结束时的最小疲劳度。

💡 解题思路

1. 题目分析：每次按键的左右手是固定的（由输入 $S_i$ 决定），左手只负责 L 的按键，右手只负责 R 的按键，两只手完全独立，互不影响。因此总疲劳度 = 左手移动距离之和 + 右手移动距离之和，可以分开计算。数据范围 $N \leq 100$，$A_i \leq 100$，非常小，但即使是 $N=10^5$ 也能用同样的 $O(N)$ 做法。

2. 算法推导：

   • 对于某一只手，假设它需要按的键依次为 $a_1, a_2, \dots, a_k$。
   • 该手初始可以放在任意位置，为了最小化疲劳度，最优策略是把手初始放在第一个按键的位置 $a_1$，这样第一次按键的移动距离为 $0$。
   • 之后每次按键，手从当前位置 $a_{i-1}$ 移动到 $a_i$，距离为 $|a_i - a_{i-1}|$。
   • 因此该手的总疲劳度 = $\sum_{i=2}^{k} |a_i - a_{i-1}|$。
   • 遍历所有 $N$ 次按键，分别维护左手和右手上一次所在的位置。当遇到某只手的按键时，若该手之前已经放置过，则累加移动距离；然后更新该手的位置为当前按键位置。

3. 边界与细节：

   • 用 ll 和 rl 分别记录左手和右手上一次的位置，初始化为 $-1$ 表示"尚未放置"。
   • 当 ll == -1 或 rl == -1 时，说明该手第一次按键，此时不累加疲劳度（因为初始放置在该位置，距离为 $0$）。
   • 注意区分 ll 为 $-1$ 和位置为 $0$ 的区别——位置 $-1$ 作为哨兵值，而实际按键位置 $A_i \ge 1$，不会混淆。

⏱️ 复杂度分析

• 时间复杂度：遍历 $N$ 次按键，每次 $O(1)$ 判断和累加，总复杂度 $O(N)$。
• 空间复杂度：仅使用常数个变量（ll、rl、ans、b、s），空间复杂度 $O(1)$。

💻 标准代码 (C++)

#include <bits/stdc++.h>
using namespace std;

int n, b, ans = 0, ll = -1, rl = -1; // ll: 左手上次位置, rl: 右手上次位置, -1 表示未放置
char s;

int main () {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        cin >> b;   // 当前按键编号
        cin >> s;   // 当前按键使用的手
        if (s == 'L') {
            // 左手之前已经放置过，累加移动距离
            if (ll != -1) ans += abs(b - ll);
            ll = b; // 更新左手位置
        }
        else {
            // 右手之前已经放置过，累加移动距离
            if (rl != -1) ans += abs(b - rl);
            rl = b; // 更新右手位置
        }
    }
    printf("%d", ans);
    return 0;
}