UVa 10037 Bridge

本題連結

題意：
　　每個人的移動速度不一樣，兩個人走時間是以較慢那個人，一次只能兩個人走過去橋的對面，然後需要有一個人把手電筒送回來，求耗費時間最少的方法。

想法：
　　先將數列P排序好，時間由小到大，本題可以分為幾種情況：

1. 只有一個人：直接走過去，時間為P[0]。
2. 兩個人：直接走過去，時間為P[1]。
3. 三個人：P[0],P[1],P[2]，時間為P[1]+P[0]+P[2]
      P[0] P[1]
      P[0]
      P[0] P[2]
4. 三個人以上：如果是偶數個人(例如4個人)，可利用P[0],P[1]不斷將最後面兩個人送到橋的對面，這樣就回到第二點，如果是奇數個人，不斷將最後面兩個送過去就回到第三點。
   將最後面兩個送到橋的對面有兩種方式，設時間最少兩人為P[0],P[1]，最後面兩個人為P[X],P[Y]：
   
   方案A(如Example)： 時間為 P[1]+P[0]+P[Y]+P[1]
      P[0] P[1]
      P[0]
      P[X] P[Y]
      P[1]
   方按B：時間為 P[X]+P[0]+P[Y]+P[0]
      P[0] P[X]
      P[0]
      P[0] P[Y]
      P[0]
   
   因此每次送最後兩個人過去的時候，要比較兩種方式的時間，如果(方案A<方案B)就使用方案A，否則使用方案B。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int Case,N,P[1001],i;
	scanf("%d",&Case);
	while (Case--)
	{
	scanf("%d",&N);
	for (i=0; i<N; i++) scanf("%d",&P[i]);
	sort (P,P+N);
	int sum=0;
	for (i=N-1; i>=3; i-=2){ //三個人以上
	int A = P[1]+P[0]+P[i]+P[1];
	int B = P[i]+P[0]+P[i-1]+P[0];
	if (A<B) sum += A;
	else sum += B;
	}
	if (i == 2) sum += (P[1]+P[0]+P[2]); //三個人
	else if (i == 1) sum += P[1]; //兩個人
	else if (i == 0) sum += P[0]; //一個人
	printf("%d\n",sum);
	for (i=N-1; i>=3; i-=2){
	int A = P[1]+P[0]+P[i]+P[1];
	int B = P[i]+P[0]+P[i-1]+P[0];
	if (A<B) printf("%d %d\n%d\n%d %d\n%d\n",P[0],P[1],P[0],P[i-1],P[i],P[1]);
	else printf("%d %d\n%d\n%d %d\n%d\n",P[0],P[i-1],P[0],P[0],P[i],P[0]);
	}
	if (i == 2) printf("%d %d\n%d\n%d %d\n",P[0],P[1],P[0],P[0],P[2]);
	else if (i == 1) printf("%d %d\n",P[0],P[1]);
	else if (i == 0) printf("%d\n",P[0]);
	if (Case) printf("\n");
	}
	return 0;
	}

view raw [UVa] 10037 Bridge.cpp hosted with ❤ by GitHub