poj 3404 Bridge over a rough river（ブリッジ問題）
2745 ワード
テーマリンク:http://poj.org/problem?id=3404
Bridge over a rough river
Time Limit: 1000 MS
メモリLimit: 65536 K
Total Submissions: 4024
Acceepted: 1644
Description
Aグループof N travelers(1≦ N ≤50)has ap proached an old and shabry bridge and wishes to cross the river a s s on as possible.However，there can be no more than tworks on the bridge atme.Besides it's neceary to light the watwith the at with。
Each trveler needs タイム seconds to cross the river on the bridge； i=1，… N （ti are integers from 1 to 100).If two trvelers are crossing together their crossing time is the time of the slost trveler.
The task is to determine minimal crossing time for the whole group.
Input
The input consists of two lineas:the first line contains the value of N and the second one contains the values of タイム （separated by one or several spaces）
Output
The out put contains one line with the result.
Sample Input
Northeastern Europe 2001、Wester n Subregion
考え方:
n==1の場合は、直接に答えを出力します。
n==2の場合、最大値を出力します。
n==3の場合、三者と
n>=4の場合、いずれも4人に転化した場合に最適解を求める。4人の川を渡る速度をAとすると、2つの戦略があります。
先にABを過ぎて、A回、CDを過ぎて、B回、つまりtemp=A+2*B+D
先にADしました。A回、またACしました。A回、つまりtemp=2*A+C+Dです。
その中の最小値を取ればいいです。つまり、2＊B＜A＋Cで方案1を選択します。そうでなければ、方案2を選択します。
コードは以下の通りです
Bridge over a rough river
Time Limit: 1000 MS
メモリLimit: 65536 K
Total Submissions: 4024
Acceepted: 1644
Description
Aグループof N travelers(1≦ N ≤50)has ap proached an old and shabry bridge and wishes to cross the river a s s on as possible.However，there can be no more than tworks on the bridge atme.Besides it's neceary to light the watwith the at with。
Each trveler needs タイム seconds to cross the river on the bridge； i=1，… N （ti are integers from 1 to 100).If two trvelers are crossing together their crossing time is the time of the slost trveler.
The task is to determine minimal crossing time for the whole group.
Input
The input consists of two lineas:the first line contains the value of N and the second one contains the values of タイム （separated by one or several spaces）
Output
The out put contains one line with the result.
Sample Input
4
6 7 6 529Northeastern Europe 2001、Wester n Subregion
考え方:
n==1の場合は、直接に答えを出力します。
n==2の場合、最大値を出力します。
n==3の場合、三者と
n>=4の場合、いずれも4人に転化した場合に最適解を求める。4人の川を渡る速度をA
先に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
",a[1]);
continue;
}
sort(a+1,a+n+1);
if(n == 2)
{
printf("%d
",a[2]);
continue;
}
if(n == 3)
{
printf("%d
",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
",sum+a[1]+a[2]+a[3]);
continue;
}
printf("%d
",sum);
}
return 0;
}