题解 P1809 【过河问题_NOI导刊2011提高（01） 】

· · 题解

培训时正巧讲到这题，以前一直不会，老师讲了一遍后也就豁然开朗了

这题是一道纯粹的贪心，所以推出规律就是最重要的一点

不妨先对所有人按所需时间ai从小到大排序

对于河此岸人数n==2的情况，很显然，耗费时间为二者中最长的一个，两人即可全部到达对岸；对于n==3的情况，先让最快的人带一人去对岸，最快的人回来，再接另一人去对岸，总共花费时间为a1+a2+a3

那么对于n>3的情况怎么来呢？我们可以先运送此岸上用时最长的两人，那么最优秀的运送方法有两种

1.最快的1载最慢的n去对岸，1回此岸继续载次慢的n-1去对岸，a1最后再回到此岸，共用时2*a1+an+a(n-1)

2.最快的人1与次快的人2去对岸，最快的人1回到此岸，最慢的人n再与次慢的人n-1去对岸，次快的人2回到此岸，共用时a1+2*a2+an

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

int i,n,a[100010];
long long ans;

void re(int &x)//快读
{
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
}

bool cmp(const int x,const int y)
{
    return x<y;
}

int main()
{
    re(n);
    for(i=1;i<=n;i++)
        re(a[i]);
    sort(a+1,a+n+1,cmp);//按用时由小到大排序
    while(n>3)
    {
        ans+=min(a[1]*2+a[n]+a[n-1],a[1]+a[2]*2+a[n]);//根据公式累加
        n-=2;//每次此岸人数减少2人
    }
    if(n==2) ans+=a[2];//此岸人数n为2或3时
    if(n==3) ans+=a[1]+a[2]+a[3];
    printf("%lld",ans);
    return 0;
}