実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 62

問題概要

100個の鍵盤が並んだピアノがあり、左から $i$ 個目を鍵盤 $i$ とする。今から $N$ 回にわたってこのピアノの鍵盤を一つずつ押すことにする。 $i$ 回目に押す鍵盤は鍵盤 $A_i$ であり、それを押す手は $S_i =$ Lのとき左手、Rのとき右手である。演奏を始める前、両手はそれぞれ好きな鍵盤の上に置くことができ、この時点での疲労度は $0$ とする。演奏中、片方の手を鍵盤 $x$ の上から鍵盤 $y$ の上へと動かすと疲労度が $|y - x|$ 増加する。このとき、演奏が終了した時点での疲労度の最小値を求めよ。

制約

$N$ は整数で $1 \leq N \leq 100$ を満たす。
$A_i$ は整数で $1 \leq A_i \leq 100$ を満たす。
$S$ はL, Rのみからなる。

考察

演奏開始後、「最初に $S_i =$ L, Rとなる鍵盤」の上にあらかじめそれぞれの手を置いておく。あとは指示の通りに手を移動させていくことで、疲労度を最小化できる。

コード

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    vector<char> S(N);
    rep(i, 0, N) cin >> A[i] >> S[i];

    int ans = 0;
    int left = 0, right = 0;
    rep(i, 0, N) {
        if (S[i] == 'L') {
            if (left == 0) left = A[i];
            else {
                ans += abs(A[i] - left);
                left = A[i];
            }
        }
        else {
            if (right == 0) right = A[i];
            else {
                ans += abs(A[i] - right);
                right = A[i];
            }
        }
    }

    cout << ans << endl;
}