問題をちゃんと読まず手こずった。
https://www.hackerrank.com/contests/unkoder-07/challenges/baton-relay
問題
N人の人が1周Lのトラックに並んでいる。
各人は基準地からX[i]のところにおり、それぞれ速度V[i]で走れる。
なお、X[i]は昇順である。
最初は1番の人がバトンを持ち、そこからリレーの要領で走る。
すなわちバトンを持った人は次の人のところまで走り、バトンを渡して静止する。
各人が最初いた位置に1回以上戻るまでの最短時間を求めよ。
解法
愚直にシミュレートするだけの実装問題。
各人が距離Lを走るまでの時間を求めよう。
バトンが1周すると各人最低1は動くので、シミュレートは高々L*N回行えばよい。
int N,L; double X[1010],V[1010],R[1010]; int ok[1010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>L; FOR(i,N) cin>>X[i]>>V[i]; double ret=0; if(N==1) { ret=L*1.0/V[0]; } else { int cur=0; while(1) { int ne=(cur+1)%N; if(X[ne]<=X[cur]) X[cur] -= L; double run=X[ne]-X[cur]; if(count(ok,ok+N,1)==N-1 && ok[cur]==0 && R[cur]+run>=L) { run = L-R[cur]; ret+=run*1.0/V[0]; break; } ret+=run*1.0/V[cur]; R[cur]+=run; if(R[cur]>=L) ok[cur]=1; X[cur]=X[ne]; cur=ne; } } _P("%.12lf\n",ret); }
まとめ
これO(LN)以下で解く解法もあるのかな?