Google code jam 2010 Round 1B B.Picking Up Chicks
問題概要
N羽の鶏が数直線状を東へ走っていく。各鶏の初期位置はXiで速度はVi、ゴールはBの座標の点である。
鶏は自分の目の前に自分より遅い鶏がいないときはViで走るが、自分より遅い鶏がいるときはそれと同じ速度で走る。
今、T秒以内にN羽のうちK羽がゴールに着くよう、クレーンで早い鶏が遅い鶏を抜かすよう吊り上げて、下ろしてやりたい。この操作は二羽の鶏が一緒に並んだ瞬間に、一瞬にして行われるものとする。
このとき、必要なクレーンの操作回数の最小値を求めよ。
各値の範囲は以下の通りである。
- 1 ≦ B ≦ 1,000,000,000;
- 1 ≦ T ≦ 1,000;
- 0 ≦ Xi ≦ B;
- 1 ≦ Vi ≦ 100;
- 1 ≦ N ≦ 50;
- 0 ≦ K ≦ N;
解法
数直線上で先頭に並んでいる鶏から一匹ずつ見て、K匹がゴールできるようにしていく。
まず、T秒以内にゴールできない鶏は抜かされないといけないことがわかる。
T秒以内にゴールできる鶏が、後ろからもっと早い鶏に追いつかれた場合を考える。
このとき、後ろからきた鶏は、前の鶏と並ぶので、結局T秒以内にゴールできることになる。したがって抜かされる必要はない。
これで、先頭からK匹ゴールさせる間に鶏の抜かされる回数を計算することができる。
ソースコード
int main() { int CS; cin>>CS; rep(cs,CS) { int n,k,b,t; cin>>n>>k>>b>>t; int x[50],v[50]; rep(i,n)cin>>x[i]; rep(i,n)cin>>v[i]; pi pr[50]; rep(i,n)pr[i]=mp(x[i],v[i]); sort(pr,pr+n,greater<pi>()); int ans=0,arrive=0,skip=0; rep(i,n) { if(double(b-pr[i].first)/pr[i].second>t)skip++; else{ arrive++; ans+=skip; if(arrive>=k)break; } } if(arrive<k)cout<<"Case #"<<cs+1<<": IMPOSSIBLE"<<endl; else cout<<"Case #"<<cs+1<<": "<<ans<<endl; } return 0; }