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;
}