【例85.3】 过河问题

解题思路

时间升序a≤b≤…≤y≤z。送最慢两人有两种最优形态：a、b摆渡代价a+2b+z，或a分别送y,z代价2a+y+z。取较小并移除y,z，最后按剩1/2/3人分别处理。

正确性说明

最慢两人要么同船过河，则需要两位最快者组织返回；要么分开过河，由最快者两次陪送最省。分别得到两式，其他人可独立继续解决，逐轮取较小实现最优。

易错点

三人总时间a+b+c；两人只需b；返回也要计时。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (auto &x : a)
            cin >> x;
        sort(a.begin(), a.end());
        long long ans = 0;
        int k = n;
        while (k > 3) {
            ans += min(a[0] + 2 * a[1] + a[k - 1], 2 * a[0] + a[k - 2] + a[k - 1]);
            k -= 2;
        }
        if (k == 3)
            ans += a[0] + a[1] + a[2];
        else if (k == 2)
            ans += a[1];
        else if (k == 1)
            ans += a[0];
        cout << ans << "\n";
    }
    return 0;
}