自动搬运

查看原文

来自洛谷，原作者为

	kkxacj Full of Hope.

搬运于2025-08-24 22:15:35，当前版本为作者最后更新于2022-11-30 15:55:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P5914 题目传送门

题意

一些旅行者想要过桥，他们只有一个火把。

火把的亮光最多允许两个旅行者同时过桥。

没有火把或者多于 $2$ 个人则不能过桥。

每个旅行者过桥都需要特定的时间，两个旅行者同时过桥时时间应该算较慢的那个。

所有旅行者最少要花费多少时间才能全部过桥?

思路

思考一下可以发现，这道题可以模拟，一共有两种过桥方案：

1. 最快的人 $a_{i}$ 拿着火把接最慢的人 $a_{j}$，一个来回需要花 $a_{1} \times 2 + a_{n} + a_{n- 1}$ 秒。

2. 最快的人 $a_{i}$ 把火把给最慢和次慢的人 $a_{j}$ 和 $a_{j - 1}$，再让第二块的人去接最快的，一个来回需要花 $a_{1} + a_{2} \times 2 + a_{n}$ 秒。

注意：

1. 在 $n < 2$ 时，第一个和第二个必须是一起走，要在后面再算！

2. $n$ 可能为 $1$，要特判！

3. 对于 $100\%$ 的数据，$1\le n\le10^5$，过桥时间均不超过 $10^9$。要开 long long!

做完这题可以去做做 P1809

code

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000005],sum; //数组开大点
int main()
{
	scanf("%lld",&n); //cin >> n
    for(int i = 1;i <= n;i++)
        scanf("%lld",&a[i]); //cin >> a[i]
    sort(a + 1,a + n + 1);
    if(n <= 2) //特判
	{
        cout << a[n];
        return 0;
    }
    while(n > 3)
    {
        sum += min(a[1] * 2 + a[n] + a[n - 1],a[1] + a[2] * 2 + a[n]);
        n -= 2;
    }
    if(n % 2 == 0)
    	sum += a[2];
    else 
    	sum += a[1] + a[2] + a[n];
    printf("%lld",sum);
    return 0;
}