一，题意：
只有一艘船，能乘2人，船的运行时间为2人中较多一人的时间，过去后还需一个人把船划回来，问把n个人运到对岸，最少需要多久。
二，思路步骤：
想办法先把用时最多的2人，运过去，再把剩下来的人中用时最多的2人运过去，依次循环下去，直到n<=3。
1,n>3时：
①最快和次快过去,最快回;最慢和次慢过去,次快回,time=s[1]+s[0]+s[n-1]+s[1]。
②最快和最慢过去,最快回;最快和次快过去,最快回,time=s[n-1]+s[0]+s[n-2]+s[0]。
选择两者中用时较少的一个策略执行。如此便将最慢和次慢送过河，对剩下n-2个人循环处理
注意：当n=1、n=2、n=3时直接相加处理即可.
2,n==3时 ①= ②= time + s[0]+s[1]+s[2];
3,n==2时 time += s[1];
4,n==1时 time += s[0]。
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int t , n ;
int s[];
cin>>t;
while(t--){
cin>>n;
int time = ;
for(int i = ; i < n ; i++){
cin>>s[i];
}
while(n>){ //当n>3时,重复方法选择最小的用时相加
time = min(time + s[]+s[]+s[n-]+s[],time + s[n-]+s[]+s[n-]+s[]);
n-=; //每次循坏过2个人
}
if(n==)time += s[]+s[]+s[];
else if(n==)time += s[];
else time += s[];
cout<<time<<endl;
}
return ;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。