题意:每次两个人坐船过河,每次过河的时间取速度较慢的那个人,问所有人过河所需最短时间。

思路:经典贪心题目,我们将时间进行从小到大排序,根据贪心思想,我们肯定需要人过了河带船回来,显然肯定要速度快的带船回来所用时间更少,所以每次我们需要运速度较慢的人过去然后他们就不用管了。接下来对特殊情况进行讨论。

时显然

时,显然船要回一次,所以肯定是速度最快的人回,

时,我们可以通过每次运两个(最慢和次慢)将情况变为前面三种情况,此时要分两种情况

类比的方法,

:通过让最慢和次慢的一起过河,从而减少一次次慢的时间,但要增加一倍次快的时间,方法是先让最快和次快过河,最快回来,最慢和次慢过河,次快再回来。即

综上问题得到解决。

时间复杂度:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm> 
#include<map>
using namespace std;
typedef long long ll;
const int N=1e5+10;
#define mst(a) memset(a,0,sizeof a)
ll a[N];
using namespace std;
int main()
{
    int n;
        while(~scanf("%d",&n)){
        ll ans=0;
        int i;
        for(i=1;i<=n;i++) scanf("%lld",&a[i]);
        sort(a+1,a+n+1);
        for(i=n;i>3;i-=2)
            if(a[1]*2+a[i-1]+a[i]<a[1]+a[2]*2+a[i])
                ans+=a[1]*2+a[i-1]+a[i];
            else ans+=a[1]+a[2]*2+a[i];
        if(i==3) ans+=a[1]+a[2]+a[3];
        else if(i==2) ans+=a[2];
        else ans+=a[1];
        printf("%lld\n",ans);
    }
    return 0;
}