Google code jam 2010 Round 1B B.Picking Up Chicks

Google Code Jam 実装問題 貪欲法

問題概要

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