题解 | #小强去春游#

算法思路

1. 人数为2人时，设 a <= b ，消耗时间为 b
2. 人数为3人时，设 a <= b <= c ，消耗时间为 a+b+c
3. 人数大于等于4时，每轮循环减少2个人，直到满足条件1或条件2；设 a <= b <= c <= d，此时有两种运的方式：

• 一种是a走4次，其中2次带一个大的，2次还船回来；即 2*a+c+d
• 另一种是a和b先过去，a回来还船，c和d过去，b回来还船；即 a+2*b+d
• 消耗时间取最小，即 min(a+2b+d,2a+c+d)

时空复杂度分析

• 时间复杂度 O(nlog n)，无序数组排序的时间复杂度
• 空间复杂度 O(n)

实际性能与空间消耗情况

• 运行时间308ms
• 占用内存800KB

代码

#include <iostream>
#include <algorithm>
using namespace std;

int process(int*nums,int n){
    if(n==1) return nums[0];
    std::sort(nums,nums+n);
    //  nums[0]最轻; nums[1]次轻;

    int ans=0;
    for (int i = n-1;i!=1;i-=2) { // 剩余两人时退出循环
        if(i==2){
            ans+=nums[0]+nums[i];//若剩下最轻的三人a<=b<=c，a载c过去，再还船回来，此时也剩下ab两人
            break;
        }
        ans+=min(2*nums[1],nums[0]+nums[i-1])+nums[0]+nums[i];
        // 若剩下有大于等于四个人，运两个人过去耗费的时间=min(a+2*b+d,2*a+c+d)
    }

    return ans+nums[1];// 剩下最轻的两人
}

int main(){
    int t;cin>>t;

    int n;
    int nums[100000];
    while(cin>>n){
        for (int i = 0; i < n; ++i)cin>>nums[i];
        cout<<process(nums,n)<<endl;
    }

    return EXIT_SUCCESS;
}