307
【北大夏令營筆記-數學題】百練1700-Crossing River
1700:Crossing River查看 提交 統計 提示 提問
總時間限製: 1000ms 內存限製: 65536kB
描述
A group of N people wishes to go across a river with only one boat, which can at most carry two persons. Therefore some sort of shuttle arrangement must be arranged in order to row the boat back and forth so that all people may cross. Each person has a different rowing speed; the speed of a couple is determined by the speed of the slower one. Your job is to determine a strategy that minimizes the time for these people to get across.
輸入
The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. The first line of each case contains N, and the second line contains N integers giving the time for each people to cross the river. There won't be more than 1000 people and nobody takes more than 100 seconds to cross.
輸出
For each test case, print a line containing the total number of seconds required for all the N people to cross the river.
樣例輸入
1
4
1 2 5 10
樣例輸出
17
來源
POJ Monthly--2004.07.18
題意：
夜裏n個人過橋，隻有一個手電筒
每個人有一個過橋時間ai,必須兩個人過去再由一個將手電筒拿回來，過橋時間由兩人中慢的決定。
求最小全部通過時間。
經典過橋問題，數學雜題
當n>=4 考慮最慢的2個 有2種情況
（速度最快和次快的每次送完慢的和次慢的要回到原岸準備下一次運送）
1 都由最快的陪過去
2 最快的2個先過去 再回來1 個 最慢的2個過去 最快的2個裏麵另外一個回來
這樣就化歸為n-2的情況
設最快的2個用時a，b，最慢的用時 y,z
第一種情況 用時a+a+y+z
第二種情況 用時a+b+b+z
選時間少的那組
n=1,2 直接過 n=3，最快的陪
AC代碼：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[1500];
int main()
{
int i,j,n,m,sum,num1,num2,flag,p;
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
memset(a,0,sizeof(a));
for(i=0;i<m;i++)
scanf("%d",&a[i]);
sort(a,a+m);
if(m==1)
printf("%d\n",a[0]);
else
if(m==2)
printf("%d\n",a[1]);
else
if(m==3)
printf("%d\n",a[0]+a[1]+a[2]);
else
{
flag=1;sum=0;
while(flag)
{
//1,2(速度最快和次快的)每次送完慢的和次慢的要回到原岸，
//因為還要留下來運送下一對最慢的和次慢的，不能隻運第一次
num1=a[1]+a[0]+a[m-1]+a[1];
num2=a[m-1]+a[0]+a[m-2]+a[0];
sum+=min(num1,num2);
if(m-3==2)//如果剩下3個人
{
sum+=a[0]+a[1]+a[2];
break;
}
if(m-3==1)//如果隻剩下1和2
{
sum+=a[1];
break;
}
m-=2;//每次都送走最慢和次慢的兩個人
}
printf("%d\n",sum);
}
}
return 0;
}
最後更新：2017-04-03 05:39:29