本文主要是介绍渡河问题（贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
现在有一群人，到了一条河旁边，想要过河，但船只有一条，一次最多能载两个人，开到了对面还需要一个人负责把船开回来，而且若多人坐船，速度还是由慢的一个决定，现在求如何分配坐船，使总时间最短。
输入
输入t组数据，每组数据第1行输入n，第2行输入n个数，表示每个人过河的时间。
输出
输出t行数据，每行1个数，表示每组过河最少时间。
样例输入
1
4
1 2 5 10
样例输出
17
#include<iostream>
#include<algorithm>
using namespace std;
int time(int a[],int left){//left河岸左边的人数 int ans=0;while(left>0){if(left==1){ ans+=a[1];return ans;}else if(left==2){ans+=a[2];return ans;}else if(left==3){ans+=a[1]+a[2]+a[3];return ans;}else{//进入后else后，最慢的2人过河，且船在河岸的左边 //策略1：最快的带最慢的——1,left过河，a[left]。1返回，a[1]。1,left-1过河，a[left-1]。1返回，a[1]。 int time1=2*a[1]+a[left-1]+a[left];//策略2：最快的带次之，最慢的和次之——1,2过河，a[2]。1返回，a[1]。left,left-1过河，a[left]。a[2]返回，a[2]。 int time2=a[1]+2*a[2]+a[left];ans+=min(time1,time2);left-=2;}}
}
int main(){int t;cin>>t;while(t--){int n;cin>>n;int a[n+1];for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);//将渡河时间排序cout<<time(a,n)<<endl; }return 0;
} 
这篇关于渡河问题（贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
