[AOJ] No. 0299 鉄道路線II
問題
方針
買い物をする駅の番号の順番を変えても影響がないので、\( d_i \) を昇順に整列させます。ここで、\( d_i < p \) を満たす最大の \( d_i \) を \( l \) とし、\( d_i > p \) を満たす最小の \( d_i \) を \( r \) とします。\( d_i = p\) を満たす \( i \) が存在しないことに注意します。ここで、\( L(s, g) \) を 左回りで 駅 \( s \) から 駅\( g \) まで行く時のコストとして、\( R(s, g)\) を右回りで 駅 \( s \) から 駅\( g \) まで行く時のコストとします。このとき、
\[\begin{eqnarray}
L(s, g) &=& \begin{cases} 100(s – g) & ( g \leq s ) \\ 100(N – (g – s)) & ( g > s ) \end{cases}\\
R(s, g) &=& \begin{cases} 100(N – (s – g)) & ( g \leq s ) \\ 100(g – s) & ( g > s ) \end{cases}
\end{eqnarray}\]
となります。最適な駅の周り方は、方向を転換して回るのが少なくとも \( 1 \) 回だけなので、全探索を行います。
全て同じ方向に進むとき
全て左回りで行動するときの最小のコストは、\( L(p, r) \) となり、全て右回りで行動するときの最小のコストは \( R(p, l) \) となります。
駅 \( d_i \) まで左回りに進んだ後、右回りで進む
\( i = 0 \) のとき
このときの最小のコストは、\( 2L(p, d_0) + R(p, d_{M – 1}) \) となります。
\( i \neq 0 \) のとき
このときの最小のコストは、\( 2L(p, d_i) + R(p, d_{i – 1}) \) となります。
駅 \( d_i \) まで右回りに進んだ後、右回りで進む
\( i = M – 1\) のとき
このときの最小のコストは、\( 2R(p, d_i) + R(p, d_{0}) \) となります。
\( i \neq M – 1 \) のとき
このときの最小のコストは、\( 2R(p, d_i) + R(p, d_{i + 1}) \) となります。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int N, M, p; int left(int s, int g) { if (g <= s) { return 100 * (s - g); } else { return 100 * (N - (g - s)); } } int right(int s, int g) { if (g <= s) { return 100 * (N - (s - g)); } else { return 100 * (g - s); } } int main() { cin >> N >> M >> p; vector<int> d(M); for (int i = 0; i < M; i++) { cin >> d[i]; } sort(d.begin(), d.end()); int l = -1; int r = -1; int kl = 200 * N; int kr = 200 * N; int idx = -1; for (int i = 0; i < M; i++) { if (kl > left(p, d[i])) { kl = left(p, d[i]); l = d[i]; } if (kr > right(p, d[i])) { kr = right(p, d[i]); r = d[i]; } } //cout << l << " " << r << "\n"; int ans = min(left(p, r), right(p, l)); // 全て左回りまたは右回り for (int i = 0; i < M; i++) { int t1; // d[i]<-p d[i]->p p->d[i-1] if (i == 0) { t1 = 2 * left(p, d[i]) + right(p, d[M - 1]); } else { t1 = 2 * left(p, d[i]) + right(p, d[i - 1]); } int t2; if (i == M - 1) { t2 = 2 * right(p, d[i]) + left(p, d[0]); } else { t2 = 2 * right(p, d[i]) + left(p, d[i + 1]); } ans = min(ans, min(t1, t2)); } cout << ans << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません