题解 P5914 [POI2004]MOS

kkxacj · 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 时，第一个和第二个必须是一起走，要在后面再算！

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;
}