Crossing River（贪心算法）

最新推荐文章于 2025-05-27 20:34:33 发布

走心小卖家.

最新推荐文章于 2025-05-27 20:34:33 发布

阅读量1.3k

点赞数

文章标签：贪心算法 c++

本文链接：https://blog.csdn.net/Quietprogrammer/article/details/104793627

版权

该博客讨论了一种使用贪心算法解决如何在有限条件下将n个人运送到对岸的优化问题。文章中提出了两种最优方案，并通过实例分析了递归和循环解决方法的优劣。最终，博主分享了一段简洁高效的代码来实现这个算法。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

只有一艘船，能乘2人，船的运行速度为2人中较慢一人的速度，过去后还需一个人把船划回来，问把n个人运到对岸，最少需要多久。
输入t组数据，每组数据第1行输入n，第2行输入n个数，表示每个人过河的时间。
输出t行数据，每行1个数，表示每组过河最少时间。
思路：
由于运送人数，每人过河所用时间差的大小等因素在每个测试样例中不同，所以本题有两种较优方案
1.最快的和次快的过河，然后最快的将船划回来；次慢的和最慢的过河，然后次快的将船划回来，时间：t[0]+2t[1]+t[n-1];（最快和次快过了河一定再让最慢次慢过河，如果n为奇数要让单着的人尽可能用时少）
2.最快的和最慢的过河，然后最快的将船划回来，最快的和次慢的过河，然后最快的将船划回来(每一次都让最快的将船划回来)时间：2t[0]+t[n-2]+t[n-1]。
一开始我用了递归的方法去计算方案中的时间t1但是空间复杂度太高，出现了Memory Limit Exceeded（内存超限）的错误
t2比较好求一个循环就可以解决
下面是我第一次写的代码（Memroy limit Exceeded)

#include<iostream>
#include<cmath>
using namespace std;
int f(int n,int a[]) //递归的思想
{
    int sum=0;
    if(n==2)
        return a[2];
    if(n==3)
        return a[1]+a[2]+a[3];