小船过河问题

小船过河问题
有一艘船，能乘2人，船的运行速度为2人中较慢一人的速度，过去后还需一个人把船划回来，问把n个人运到对岸，最少需要多久。先将所有人过河所需的时间按照升序排序，我们考虑把单独过河所需要时间最多的两个旅行者送到对岸去，有两种方式：
1.最快的和次快的过河，然后最快的将船划回来；次慢的和最慢的过河，然后次快的将船划回来，所需时间为：t[0]+2*t[1]+t[n-1]；
2.最快的和最慢的过河，然后最快的将船划回来，最快的和次慢的过河，然后最快的将船划回来，所需时间为：2*t[0]+t[n-2]+t[n-1]。
算一下就知道，除此之外的其它情况用的时间一定更多。每次都运送耗时最长的两人而不影响其它人，问题具有贪心子结构的性质。
 

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a[1000],t,n,sum;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
sum=0;
for(int i=0;i<n;i++) scanf("%d",&a[i]);
while(n>3)
{
sum=min(sum+a[1]+a[0]+a[n-1]+a[1],sum+a[n-1]+a[0]+a[n-2]+a[0]);
n-=2;
}
if(n==3) sum+=a[0]+a[1]+a[2];
else if(n==2) sum+=a[1];
else sum+=a[0];
printf("%dn",sum);
}
}

最后

以上就是害羞荷花为你收集整理的小船过河问题的全部内容，希望文章能够帮你解决小船过河问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。