Codeforces 363 Div2 A. Launch of Collider
問題概要
粒子の数字(座標)とそれに対応するLRのどちらかが与えられる。Lの場合、その座標から左に動かすことができ、Rの場合、その座標から右に動かすことができる。粒子が1秒で1マス分、指定された 方向に動くことができる。最短何秒でぶつかるか。またはぶつかることがないか。
解法
小さな座標から大きな座標の方向へ、隣どおしの粒子を確認していく。左の粒子がRで右の粒子がLの時、粒子どおしがぶつかる。その中で、最短のものを求とめ、もし、一度も粒子がぶつかることがなければ、-1を出力すればいい。
私の回答だと、隣どおししか確認していないから、ダメなきがしたけど、実験したら、よさそう。
ミス
特になし。
コード
#include <iostream> #include <algorithm> #include <vector> #include <cstdio> #include <cstring> using namespace std; typedef vector<int> vint; #define rep(i,n) for(int i=0;i<(n);i++) int main(void){ int n; scanf("%d", &n); string s; cin >> s; vint v(n); rep(i, n) scanf("%d", &v[i]); int ans = 1e9; for (int i = 0; i < n - 1; ++i){ if(s[i] == 'R' && s[i + 1] == 'L'){ ans = min(ans, (v[i + 1] - v[i]) / 2); } } if(ans == 1e9)printf("-1\n"); else printf("%d\n", ans); return 0; }