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