题目链接: http://poj.org/problem?id=1700
1. 当1个人时: 直接过河 t[0].
2. 当2个人时: 时间为较慢的那个 t[1].
3. 当3个人时: 时间为 t[0]+t[1]+t[2].
4. 当4个以上的人时, 将t[0] 和 t[1]当作搬运工. 两种方案:
- 最快和次快的过去, 最快的回来, 最慢和次慢的过去, 次快的回来, 这样就将最慢和次慢的送过去了. 时间: t[0]+2*t[1]+t[i]
- 最快的依次送最慢和次慢的过去再回来, 时间: 2*t[0]+t[i-1]+t[i]
以上方案每次就将最慢的和次慢的送过河, 每次送走两个人, 当将其他人送完之后, t[0]和t[1]再过河.
#include <iostream>
#include <algorithm>
using namespace std;
bool comp(int a,int b){
return a<b;
}
int main(){
int m,n,t[],i,sum;
cin>>m;
while(m--){
cin>>n;
sum = ;
for(i=;i<n;++i)
cin>>t[i];
sort(t,t+n,comp);
for(i=n-;i>;i-=){
//把t[0]和t[1]当成搬运工,最后返回到原地
int t1 = t[]+*t[]+t[i];//最快的(即所用时间t[0])和次快的过河,然后最快的将船划回来,再次慢的和最慢的过河,然后次快的将船划回来
int t2 = *t[]+t[i-]+t[i];//最快的和最慢的过河,然后最快的将船划回来,再最快的和次慢的过河,然后最快的将船划回来
sum += t1>t2?t2:t1;
}
if(i==) //3people left
sum += t[]+t[]+t[];
else if(i==) //2 people left
sum += t[];
else // 1 people left
sum += t[];
cout<<sum<<endl;
}
return ;
}
-->