2020年牛客アルゴリズム入門課練習試合2のC-移動中の川

テーマは牛市の生存した先民が流星群の後、痛みを我慢してこの土地を離れ、移動を選択し、移動の途中で川を渡る必要があることを描いている.牛市の木々が流星群でひどく破壊されたため、彼らはボートを1隻しか作らず、船が小さすぎて、一度に2人しか乗れなかった.牛市の先住民たちは一人一人が船を漕ぐスピードが違うので、一人一人が川を渡る時間Tを持っていて、船のバランスを保証するために、二人が着ているときは、遅い人のスピードで船を漕ぐ必要があります.つまり、船が対岸に着いた時間は船で川を渡る時間が長い人の時間を待つ必要があります.現在、N人の渡河時間Tが知られていますが、少なくともどのくらいの時間をかけて、すべての人が川を渡ることができますか.
入力説明:ファイルの第一行為先民の人数N(N≦100000)を入力し、以下にN行があり、各行に1つの整数は各人の渡河時間である.
出力説明:出力ファイルには、すべての人が川を渡る最小の渡河時間を示す数しか含まれていません.
入力4 5 7 11 16
出力42
説明まず1、2まず川の対岸まで7、それから1が戻ってきて5、3、4が川の対岸まで16、2が戻ってきて7、1、2が川の対岸まで7
問題:
問題解析:(以下N人の速度はabcd…でそれぞれ表され、速度昇順で並べ替えられる)1、n=1の場合、timeはa 2、n=2の場合、timeはb 3、n=3の場合、timeはa+b+c(aは任意の人と川を渡って、aは更に帰って、更に残りの人と川を渡ります)4、n>=4の时、问题はとても复雑で、任意の2人が川を渡るため、更に川の中の1つを过ぎて更に帰ってくるのは多くの情况があって、私达はここで分析してテーマを観察する必要があります私达は川の中で2つの最も重要な点の方案を発现することができます【1】川を渡った2人は、最も長い時間を費やした人がこれについて決めるので、最も遅いdと遅いcを一緒に置くことができ、このように遅い時間cは無視されます.【2】戻ってきた一人が、時間をかけて一人で決めていることに対しては、最速のaに他の人を一人ずつ送ってもらい、最速のaによって船を送り返して上記の案を実現することができますn=4の場合(以下N人の速度はabcd…で示し、速度昇順で並べ替えます)【()内に時間がかかることを示します】
上記のシナリオを実現する:シナリオ【1】abcd ab(b)過去a(a)戻りcd(d)過去b(b)戻りab(b)過去に費やした時間:a+3 b+d
シナリオ【2】abcd ad(d)過去a(a)過去ac(c)過去a(a)過去ab(b)過去に費やした時間:2 a+b+c+d
計算サンプル:次にサンプル{1,2,5,10}シナリオ【1】時間=17シナリオ【2】時間=19を与えるので、シナリオ【1】で最も時間がかかり、時間は17
しかし、データ{1,2,2,10}スキーム【1】時間=17スキーム【2】時間=16を修正すると、今回はスキーム【2】にかかる時間が最も短く、時間は16である.
2つのシナリオの所要時間を約定すると、シナリオ【1】:2 bシナリオ【2】:a+cは、最も速いaと次の速いbと次の遅いcにかかる時間の決定的な要因があることを見ることができ、2 bとa+cを比較し、最も時間のかかるシナリオを選択するだけでよい.
n>4の場合、最も速い前の2人で最も遅い後の2人を運ぶことができ、輸送が終わると人数が2減少すると表すことができます.

#include 
using namespace std;

int a[100005];
int crossRiver(int n,int*a)
{
	if(n==0)	return 0;
	if(n==1)	return a[0];
	else if(n==2)	return a[1];
	else if(n==3)	return a[0]+a[1]+a[2];
	else
	{
		int t1=a[n-1]+a[0]+a[n-2]+a[0];
		int t2=a[1]+a[0]+a[n-1]+a[1];
		int t;
		t=t1>t2 ? t2:t1;
		return t+crossRiver(n-2,a); 
	}
}