洛谷P1809 过河问题 题解

题目链接：P1809 过河问题

题意：

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

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

现在已知 \(n\) 个人的渡河时间 \(a_i\) ，cxy 想要你告诉他，他们最少要花费多少时间，才能使所有人都过河。

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

输入格式：

输入文件第一行为人数 \(n\) ，以下有 \(n\) 行，每行一个数。

第 \(i+1\) 行的数为第 \(i\) 个人的渡河时间 \(a_i\) 。

输出格式：

输出文件仅包含一个数，表示所有人都渡过河的最少渡河时间

数据范围：

对于 \(100\%\) 的数据满足 \(n \le 10^5\) 。

这道题和经典的过河问题不一样，经典的过河问题是 \(a+b\) ，而它是 \(\max\{a,b\}\) 。

因此用最小花费的人去送不一定是最优方案了。

不失一般性，假设 \(a_i\) 单调递增。

首先考虑 \(3\) 个人的情况，这个时候用最小花费的人送确实是最小的。

但是 \(4\) 个人的情况就不一定了，通过暴力枚举大部分情况，可以发现最优解有两种情况 \[ b+a+c+a+d+a = 3a+b+c+d \\c+a+d+b+b = a+2b+c+d \] 其他的情况可以很容易排除。

考虑推广这两种策略。

• 用最小花费的人去送掉一个人然后回来

• 用最小和次小去送掉两个人，然后回来

设 \(f_i\) 表示 \(i\) 个人的方案数，则有 \[ f_i = \min\left\{f_{i-1} + a_1 + a_i,~f_{i-2} + a_1 + 2\times a_2 + a_i\right\} \] 边界：\(f_1 = a_1,f_2 = a_2\)

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))

int n,a[N],f[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n); f[1] = a[1]; f[2] = a[2];
    for(int i=3; i<=n; i++)
    down(f[i] = f[i-1] + a[1] + a[i], f[i-2] + a[1] + 2*a[2] + a[i]);
    cout << f[n] << '\n';
    return 0;
}