UVa 11661 : Burger Time?
UVa演習 2014/6/8 (日) 問3
問題リンク:http://uva.onlinejudge.org/external/116/11661.html
問題概要:
長さLの文字列が与えられる
文字列の要素は次の4つのうちのいずれか
'R' : レストラン
'D' : ドラッグストア
'Z' : レストラン & ドラッグストア
'.' : 何もない
レストランとドラッグストアの距離の最小値を求めよ
解法:
左から右へ見ていき、一番最後に見たレストランの場所とドラッグストアの場所を覚えておく
RかDがくる度に場所を更新しつつ距離を計算する
Zがあれば0
コード:
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) using namespace std; const int IINF = INT_MAX; char S[2000010]; void calc(int R,int D,int &ans){ if( R == -1 || D == -1 ) return; ans = min(ans,(int)abs(R-D)); } int main(){ int L; while( cin >> L, L){ int R = -1, D = -1, ans = IINF; rep(i,L) { cin >> S[i]; if( S[i] == 'R' ) { R = i; calc(R,D,ans); } else if( S[i] == 'D' ) { D = i; calc(R,D,ans); } else if( S[i] == 'Z' ) ans = 0; } cout << ans << endl; } return 0; }