Google Code Jam 2011 Round 1B B. Revenge of the Hot Dogs
これは本番中気づくべきだった……
問題概要
数直線上のp[i]の位置にv[i]人のホットドッグ売りがいる。
彼らはどの二人も最低距離D[m]だけ離れていないといけないので、移動しなければならない。
移動速度は一律1m/sである。
全員が最低D[m]離れるまでにかかる時間の最小値を求めよ。
v[i]の合計は10^6以下
方針
時間Tで、距離D以上離れられるかどうかは、最も左の人から順に
左に行けるだけ行く(T歩くか、隣の人+Dのとこまで歩く)ことを繰りかえして、最後の人までDの距離離れられるか見ることにより確かめられる。
あとはTを動かして二分探索する。
早退誤差を1e-6以下にすればよいので、ループは120回くらい回すようにした。
(while(hi-lo>1e-7)だと精度の関係でループが終了しない)
ソースコード
int n,d,c,p[1000000]; bool ok(double t){ double left=-1e15; rep(i,n){ left=max(left+d,p[i]-t); if(left-p[i]>t+0.000000001)return 0; } return 1; } int main(){ int T; cin>>T; rep(cs,T){ cerr<<cs+1<<endl; cin>>c>>d; n=0; rep(i,c){ int v,x; cin>>x>>v; rep(j,v)p[n++]=x; } sort(p,p+n); double lo=0,hi=1e15,mid; rep(i,120){ mid=(lo+hi)/2; if(ok(mid))hi=mid; else lo=mid; } cout<<"Case #"<<cs+1<<": "; printf("%.7f\n",lo); } return 0; }