首页 > 代码库 > poj 3404 Bridge over a rough river（过桥问题）

poj 3404 Bridge over a rough river（过桥问题）

2024-07-15 13:45:52   221人阅读

题目链接：http://poj.org/problem?id=3404


Bridge over a rough river
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 4024 Accepted: 1644

Description

A group of N travelers (1 ≤ N ≤ 50) has approached an old and shabby bridge and wishes to cross the river as soon as possible. However, there can be no more than two persons on the bridge at a time. Besides it‘s necessary to light the way with a torch for safe crossing but the group has only one torch.

Each traveler needs ti seconds to cross the river on the bridge; i=1, ... , N (ti are integers from 1 to 100). If two travelers are crossing together their crossing time is the time of the slowest traveler.

The task is to determine minimal crossing time for the whole group.

Input

The input consists of two lines: the first line contains the value of N and the second one contains the values of ti (separated by one or several spaces).

Output

The output contains one line with the result.

Sample Input

4
6 7 6 5

Sample Output

29

Source

Northeastern Europe 2001, Western Subregion


 思路：

      n==1时，直接输出答案

      n==2时，输出最大值

      n==3时，输出三者和

      n>=4时，两种策略，均转化成4人时的情形求最优解。设4人过河速度为A<B<C<D，那么有两种策略：

      先AB过，A回，CD过，B回，即temp=A+2*B+D

      先AD过，A回，再AC过，A回，即temp=2*A+C+D（忘了这种情况）

然后取其中的最小值即可。也就是说，在2*B<A+C时选方案1，否则选方案2.


代码如下：

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdlib>
#include <climits>
#include <ctype.h>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
#define PI acos(-1.0)
#define INF 0x3fffffff
//typedef long long LL;
//typedef __int64 LL;
const int M = 1017;
int main()
{
	int n;
	int a[M];
	int i;
	while(~scanf("%d",&n))
	{
		for(i = 1; i <= n; i++)
		{
			scanf("%d",&a[i]);
		}
		if(n == 1)
		{
			printf("%d\n",a[1]);
			continue;
		}
		sort(a+1,a+n+1);
		if(n == 2)
		{
			printf("%d\n",a[2]);
			continue;
		}
		if(n == 3)
		{
			printf("%d\n",a[1]+a[2]+a[3]);
			continue;
		}
		int sum = 0;
		while(n)
		{
			if(2*a[2] < a[1]+a[n-1])
			{
				sum+=a[1]+2*a[2]+a[n];
				n-=2;
			}
			else
			{
				sum+=2*a[1]+a[n-1]+a[n];
				n-=2;
			}
			if(n <= 3)
				break;
		}
		if(n == 1)
			sum+=a[1];
		else if(n == 2)
			sum+=a[2];
		else if(n == 3)
		{
			printf("%d\n",sum+a[1]+a[2]+a[3]);
			continue;
		}
		printf("%d\n",sum);
	}
	return 0;
}




联系
我们