贪心算法：求过河的最短时间

描述：N位旅行者在夜里过桥需要借助手电筒。但N个人中只有一个手电筒，而且桥同时只能让两个人过。每个人单独过桥所需时间已知，但如果两个人同时过桥则所需时间是走得慢的那个人单独过桥所需的时间。

要求：设计一个方案，让这N个人尽快过桥，计算这N个人的最短过桥时间。

此如：有甲乙丙丁四个人，他们过河所需的时间分别是1，2，5，10。让最快的2个人先过桥，然后让跑的最快的人回去接剩下的人。 例如：先让甲乙过去(2分钟)，甲回来(1分钟)，甲丙过去(5分钟) 甲回来(1分钟)，甲丁再过去(10分钟)，总共需要19分钟。

输入：第一行N(表示有N个人要过河)

第二行是N个整数S，表示这N个人过河所需时间(0

输出：所有人过河的最短时间

样例输入：4

1 2 5 10

样例输出：17

阅读题目我们可以知道，这是一道贪心算法的题目，这道题的关键就在于如何安排几人的过河顺序和返回顺序。

如例子所述，有甲乙丙丁四人，且过河速度分别为1，2，5，10。而且由于两人过河时间取决于最慢的那个人，所以我们可以让跑得最快的和跑第二快的，也就是甲和乙两人最先过去，花费的时间是乙的过河时间2分钟，然后让最快的，也就是甲把手电筒送回来，花费1分钟，然后让走的最慢的两人，也就是丙和丁一起过去，花费10分钟，再让早就在对岸的乙将手电筒送回来，花费2分钟，最后甲乙两人一起过桥，花费两分钟，最终用时2+1+10+2=17，符合样例输出。

最后贴上代码，因为是萌新写的，如有错误还请包涵和指正。

#include

using namespace std;

int N;

int arr[510]={0};

int main(){

cin>>N;

for(int i=0;i

cin>>arr[i];

}

sort(arr,arr+N);

int sum=0,sum1=N;

int min=arr[0],secmin=arr[1];

while(sum1>3){

int s1=secmin+min;//两人一起过去，最快的人一人回来

int s2=arr[N-1]+secmin;//最慢的两人一起过去，第二快的人回来

sum=sum+s1+s2;//当前花费的总时间

sum1-=2;//此时还没过桥的人数

}

if(sum1==3) sum=sum+min+secmin+arr[2];//如果三人剩没过河，那么过河时间就是三人相加

if(sum1==2) sum=sum+secmin;//如果剩两人，过河时间就是第二快的人的过河时间

cout<<"过河时间为"<

return 0;

}

相关文章