小叶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