小叶OJ 2716: 过河问题 ← 贪心算法
【题目来源】
http://xiaoye.ac.cn/problem.php?id=2716
【题目描述】
有 n 个人要渡河，但只有一条小船，这条小船一次只能坐下最多两个人，并且只有一副船桨。每个人划船的速度不一样，如果两个人一起上船，由于重量变大，划船的速度相当于是划船速度最慢的那个人速度。假设给出每个人单独划船过河所花费的时间 Ti，请问所有人都过河的总时间最短的时间？
【输入格式】
输入两行，第一行是一个整数，表示要过河的 n 个人。
第二行，是 n 个整数，按速度从快到慢排序好的每个人划船过河的时间。
【输出格式】
输出一行，给出所有人过河所花费最短的时间。
【输入样例】
4
1 2 5 10
【输出样例】
17
【算法分析】
● 将各个过河时间从小到大排序并存在数组 a 中，当 n≥4 时，过河方案为：
方案一：最快的和次快的过河，然后最快的回来，再次慢的和最慢的过河，然后次快的回来。时间为 a[1]+2*a[2]+a[n]。
方案二：最快的和最慢的过河，然后最快的回来，再最快的和次慢的过河，然后最快的回来。时间为 2*a[1]+a[n-1]+a[n]。
根据比较结果，将所选方案的时间累加到总时间 s 中，并将人数 n 减少 2，因为每次循环处理了两个人过河。
【算法代码】
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
int a[n+5];
for(int i=1; i<=n; i++) cin>>a[i];
sort(a+1,a+n+1);
int s=0;
while(n>=4) {
if(2*a[1]+a[n-1]+a[n]>2*a[2]+a[1]+a[n]) {
s+=2*a[2]+a[1]+a[n];
} else s+=2*a[1]+a[n-1]+a[n];
n-=2;
}
if(n==3) s+=a[1]+a[2]+a[3];
else if(n==2) s+=a[2];
else s+=a[1];
cout<<s<<endl;
return 0;
}
/*
in:
4
1 2 5 10
out:
17
*/
【参考文献】
https://blog.csdn.net/u013596478/article/details/105016223
https://mp.weixin.qq.com/s/a9Y2YTpjjmdv2JzI3EtAVw