贪心算法-过河问题
题目描述：几个人过河，每次过两人一人回，速度由慢者决定，问过河所需最短时间。
先将所有人过河所需的时间按照升序排序，我们考虑把单独过河所需要时间最多的两个旅行者送到对岸去，有两种方式：
1.最快的和次快的过河，然后最快的将船划回来；次慢的和最慢的过河，然后次快的将船划回来，所需时间为：t[0]+2*t[1]+t[n-1]；
2.最快的和最慢的过河，然后最快的将船划回来，最快的和次慢的过河，然后最快的将船划回来，所需时间为：2*t[0]+t[n-2]+t[n-1]。
如图所示：
如果2t[2] < t[1]+t[n-1]选方法1，反之选方法2。
代码实现：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | /**************************************************************** * Description: CrossRiver 过河问题 * Author: Alex Li * Date: 2023-07-02 20:43:56 * LastEditTime: 2023-07-02 21:14:29 ****************************************************************/ #include<iostream> #include<algorithm> using namespace std; int n,t[10001],sum; int main(){ sum = 0; cin>>n; for(int i=1;i<=n;i++) cin>>t[i]; sort(t+1,t+n); while(n > 3){ sum += min( t[1]+2*t[2]+t[n] , 2*t[1] + t[n-1] + t[n]); n -= 2; } if(n == 3)sum += t[3] + t[1] +t[2]; if(n == 2)sum += t[2]; cout<<sum; return 0; } |
测试数据：(2021年普及组15题)
输入：
4
1 2 4 8
输出：15
洛谷：P1809