1. 题目源地址：http://poj.org/problem?id=1700
2. 解题思路：
两种过河策略：
(1) 用速度最快的那个每次将人载过河，再回来载其他的人。
(2) 用速度最快的和次快的循环载人，即最快的和次快的先过河，次快的留下，最快的回来，接着最慢和次慢的人过河，次快的回来。
3. 解题代码：
#include<iostream>
#include<algorithm>
#include<math.h>
#define MAX 1005
using namespace std;
int main()
{
int caseNum,n,i,sum;
int person[MAX];
cin>>caseNum;
while(caseNum--)
{
cin>>n;
for(i=0;i<n;i++)
cin>>person[i];
sort(person,person+n);
sum=0;
for(i=n-1;i>2;i=i-2)
{
int tmp1 = 2*person[0] + person[i] + person[i-1];//策略1:最快的载人
int tmp2 = person[0] + 2*person[1] + person[i];//策略2:最快的和次快的循环载人
sum += min(tmp1, tmp2);
//cout<<tmp1<<" "<<tmp2<<" "<<sum<<endl;
}
if(i == 2) sum += person[0] + person[1] + person[2];//剩下三个人
if(i == 1) sum += person[1];//剩下两个人
if(i == 0) sum += person[0];//剩下一个人
cout<<sum<<endl;
}
return 0;
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/163024.html
