小强去春游

当人数小于3的时候, 均仅有一种最优解
当人数大于3的时候, 最重的两个人有两种过河方法:
假设四个人体重为:
方法一: a和d先过河, 然后a再回来接c, 最后a再把船还回来, 此时需要时间
方法二: a和b先过河, 然后a再回来还船, c和d再过河, 最后b把船还回来, 此时需要时间
一直从这两个方法中抉择, 最后到达人数小于3的情况

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long

void slove() {
    int n; cin >> n; vector<int> a(n);
    for(int &t : a) cin >> t;
    sort(a.begin(), a.end());

    int l = 0, r = n - 1, ans = 0;
    while(r >= 3){
        ans += min(a[0] + a[r] + a[0] + a[r - 1], a[0] + a[1] + a[1] + a[r]);
        r -= 2;
    }
    if(r == 2) ans += a[0] + a[1] + a[2];
    else if ( r == 1) ans += a[1];
    else ans += a[0];

    cout << ans << endl;
}

signed main() {
    int T; cin >> T; while(T--) slove();
}

T = int(input())
for _ in range(T):
    n = int(input())
    nums = [int(i) for i in input().split()]
    nums.sort()
    time_min = 0
    while len(nums) >= 4:
        # 每次送走最重的两个人，按楼主说的比较两种方案的时间较短者
        time_min += min(nums[-1] + nums[-2] + nums[0] * 2, nums[0] + nums[1] * 2 + nums[-1])
        # 送走之后讲最重的两个***出列表
        nums.pop(-1)
        nums.pop(-1)
    if len(nums) == 3:
        time_min += sum(nums)
    elif len(nums) == 2:
        time_min += max(nums)
    print(time_min)
        

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

int helper(int n, vector<int>& weights){
    //先从小到大排序便于贪心
    if(n == 0) return 0;
    sort(weights.begin(), weights.end());
    //贪心，当人数不小于4时，我们可知一定是先让最重的过去是最优，此时最优解有两种情况：
    //（1）每次都让最轻的分别把最重和次重的运过去，耗时2 * weights[0] + weights[n - 1] + weights[n - 2]
    //（2）第一次先让最轻和次轻过去，最轻回去，最重和次重一起过去，次轻回来，耗时 2*weights[1] + weights[0] + weights[n - 1]
    //故每次取两者最小值即可
    //可知最后留下来的不是最轻的3个人，就是最轻的2个人
    //这时3个人，那就是weights[0] + weights[1] + weights[2];
    //这时2个人，那就是weights[1];
    //最后特殊情况只有1个人不要忘记
    int minTime = 0;
    while(n >= 4){
        minTime += min(2 * weights[0] + weights[n - 1] + weights[n - 2],
                       2 * weights[1] + weights[0] + weights[n - 1]);
        n -= 2;
    }
    if(n == 3){
        minTime += weights[0] + weights[1] + weights[2];
    }
    else if(n == 2) minTime += weights[1];
    else minTime += weights[0];
    return minTime;
}


int main(){
    int times;
    cin >> times;
    while(times-- > 0){
        int n;
        cin >> n;
        vector<int> weights(n);
        for(int i = 0; i < n; i++){
            cin >> weights[i];
        }
        cout << helper(n, weights) << endl;
    }
}

#include<iostream>
#include<vector>
#include<algorithm>

int main(){
    int n = 0;
    std::ios::sync_with_stdio(0),std::cin.tie(0);
    std::cin >>n;
    for(int i=0;i<n;i++){
        int length = 0;
        std::vector<int>temp_ans;
        std::cin >> length;
        for(int i=0;i<length;i++){
            int temp = 0;
            std::cin>>temp;
            temp_ans.push_back(temp);
        }
        std::sort(temp_ans.begin(),temp_ans.end());
        int ans = 0;
        while(length>=4){
            int plan1 = temp_ans[0]*2 + temp_ans[length-2]+temp_ans[length-1];
            int plan2 = temp_ans[0]+temp_ans[1]*2+temp_ans[length-1];
            ans += std::min(plan1,plan2);
            length-=2;
        }
        if(length==3){
            ans+=temp_ans[0]+temp_ans[1]+temp_ans[2];
        }
        if(length==2){
            ans+=temp_ans[1];
        }
        if(length==1){
            ans+=temp_ans[0];
        }
        std::cout<< ans << std::endl;
    }
}

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 输入组数
        int T = in.nextInt();
        in.nextLine();
        while (T-- > 0) {
            // 输入人数
            int n = in.nextInt();
            in.nextLine();
            int[] weights = new int[n];
            String[] s = in.nextLine().split(" ");
            for (int i = 0; i < n; i++) {
                weights[i] = Integer.parseInt(s[i]);
            }
            Arrays.sort(weights);
            int res = 0;
            while (n >= 4) {
                // 最小的带最大的过去，然后回来
                int plantOne = weights[n - 1] + weights[0] * 2 + weights[n - 2];
                int plantTwo = weights[1] * 2 + weights[0] + weights[n - 1];
                res += Math.min(plantOne, plantTwo);
                n -= 2;
            }
            if (n == 3) {
                res += weights[0] + weights[1] + weights[2];
            }
            if (n == 2) {
                res += weights[1];
            }
            if (n == 1) {
                res += weights[0];
            }
            System.out.println(res);
        }
    }