• 前言
• 题目大意
• 思路
• 代码
• 总结

前言

一眼数学题的贪心。

题目大意

有一个大晴天，Oliver与同学们一共N人出游，他们走到一条河的东岸边，想要过河到西岸。而东岸边有一条小船。

船太小了，一次只能乘坐两人。每个人都有一个渡河时间T，船划到对岸的时间等于船上渡河时间较长的人所用时间。

现在已知N个人的渡河时间T，Oliver想要你告诉他，他们最少要花费多少时间，才能使所有人都过河。

注意，只有船在东岸（西岸）的人才能坐上船划到对岸。

对于100%的数据满足N≤100000。

思路

本题的贪心思路我管它叫大小分配问题。首先肯定要对时间排序了。之后可以发现，如果只剩 $3$ 或 $3$ 以内个人，无非就两种情况：

两个人时：

• 一起过去，$a[1]+a[2]$ 个时间

三个人时：

• 第一个跟第三个过去，第一个回来，第二个和第一个过去 $a[3]+a[1]+a[2]$，实际上是 $\max(a[1],a[3])+a[1]+\max(a[1]+a[2])$，由于排序了吗，所以不用比大小了。

之后考虑人数大于 $3$ 的情况。

这就是大小分配的关键。首先可以发现，一次送俩最大的直到变成上面的情况好像最优，考虑怎么分配。

• 小+大的组合。让 $a[1]$ 和 $a[n]$ 组队，这样回来接$a[n-1]$ 的时间用时最短。
• 大+大的组合。先让 $a[1]$ 和 $a[2]$ 过去，如果要去俩的话肯定这样最优。之后让 $a[1]$ 把船划回来。然后大大组合，$a[n]$ 和 $a[n-1]$ 过去，最后让 $a[2]$ 把船划回来。

之后的话大+小相同，小+小没有任何意义，之后的快速来回没了。

这个可以想到是对的。如果让小的先走，那么后来划船回来的时间就没法省了，完成的事情还是一样的。让小的留在最后回来就是让快速划船回来的时间节省。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MAXN=1e5+5;
ll n,a[MAXN];
int main(){
    scanf("%lld",&n);
    for (int i = 1; i <=n ; ++i) {
        scanf("%lld",&a[i]);
    }
    sort(a+1,a+n+1);
    ll ans=0;
    while (n>3){
        ans+= min(a[n]+a[1]+a[n-1]+a[1],a[2]+a[1]+a[n]+a[2]);
        n-=2;
    }
    if(n==2){
        ans+=a[2];
    }else{
        ans+=a[1]+a[2]+a[3];
    }
    printf("%lld\n",ans);
    return 0;
}

总结

归纳了一种贪心方法——大小分配问题。这个问题的关键之处在于使用小的时间来节省大的时间的流动，通常可以在“大”达到目的之后的还原上节省。