PKU 1700 Crossing River

気分転換にPKUの簡単な問題を10問強やった。
三月中に（累計）正解数150問を目標にしよう。

そういえばPKU Judge Onlineの問題を1000問解くと赤コーダーになれるという噂があったような。
頑張って1000問解いて噂の真偽を確かめたいと思うｗ

面白かった問題の解説を書いておく。

n人がボート１艇だけを使って川を渡りたい。
ボートは二人乗りで、川を片道渡るのにかかる時間は乗っている人のうち、
遅いほうの（一人の場合はその人の）ボートを漕ぐスピードである。
整数nと、n人それぞれのボートを漕ぐスピードが与えられたとき、全員が川を渡るのにかかる最小の時間はいくらか。

貪欲法で最適解を求めることが可能。
n=1,2,3の時は少し考えれば自明。
n=4以上の時は、「一番遅いほうの二人」を渡す方法のに次の二つの方法が考えられる。
人を漕ぐ速さの順に0,1, ... ,n-2,n-1とすると

一番速い人を使って（(0,n-1)行く→0戻る→(0,n-2)行く→0戻る）遅い二人を渡す。
二人を一度に渡す。ボートは1の人が回収する。（(0,1)行く→0戻る→(n-1,n-2)行く→1戻る）

これを繰り返すことでn≦3の場合に帰着することができる。

	int t; cin>>t;
	while(t--)
	{
		int n; cin>>n;
		
		int s[n];
		rep(i,n)cin>>s[i];
		sort(s,s+n);
		
		int ans=0;
		while(n>3)
		{
			int a=s[0]*2+s[n-2]+s[n-1];
			int b=s[0]+s[1]*2+s[n-1];
			//dbg(a),dbg(b);
			ans+=min(a,b);
			n-=2;
		}
		if(n==3)ans+=accumulate(s,s+n,0);
		if(n<3)ans+=s[n-1];
		cout<<ans<<endl;
	}

（main関数部分のみ）