题目链接：Codeforces 1091F

Bob 是一只鸭子，他想去 Alice 那里，这段路程可以分为 $n$ 段，Bob 位于最左侧，Alice 位于最右侧。每一段都有一个长度 $l_i$（单位为米），还有一个地形：草、水、山。

Bob 有 $3$ 种运动类型：游泳、步行、飞行。他可以在这些类型之间任意切换，也可以在任何时间改变运动方向。Bob 只能在水上游泳，只能在草地上步行，但是在任何地形上都能飞行。飞行、游泳、步行 $1$ 米分别需要 $1,3,5$ 秒。

Bob 的能量是有限的。每游泳或步行 $1$ 米都可以增加 $1$ 个单位的能量，而每飞行 $1$ 米会消耗 $1$ 个单位的能量。起初他的能量为 $0$。

请求出他到达 Alice 所在位置的最短时间。

数据范围：$1\le n\le 10^5$，$1\le l_i\le 10^{12}$。

Solution

贪心好题啊！QAQ

我们考虑贪心地在山上飞行，在水中游泳，在草地上步行，记录下花费的时间和能量。这样的方案可能会导致两种问题：在飞行时能量不够；或者在最后剩下了一些能量。

• 缺乏能量
  如果我们缺乏能量了，那么我们可以选择在“原地”步行或游泳来获得能量。例如，我们向后移动 $0.5$ 米，再向前移动 $0.5$ 米，就可以获得 $1$ 个能量）。为了更快的获得能量，显然这个过程要尽可能地在水上游泳完成。换言之，我们所有的能量都要尽可能在第一个水上获得；如果在缺少能量的地方之前没有水，那只能在草地上获得能量。
• 多余能量
  如果我们在最后有多余的能量，肯定要将一些步行或游泳换成飞行。注意转化 $1$ 米的移动需要多消耗 $2$ 个单位的能量（因为不但没有得到能量还额外消耗了 $1$ 个单位的）。又因为步行的速度更慢，因此要尽可能将步行转换为飞行。这个部分的细节比较多。考虑一种情况：如果我们过早地进行转换，可能在某个地方耗尽能量。由于不能在任何一个时刻使能量变为负数，我们设当前时刻经过的草地长度为 $G$，当前能量为 $S$，那么可以转化的能量不大于 $G$，也不超过 $\frac{S}{2}$。故我们可以直接将 $G$ 更新为 $\min\left(G,\frac{S}{2}\right)$。最后我们把 $G$ 米的步行转换为飞行，把 $\frac{S}{2}-G$ 的游泳转换为飞行。

时间复杂度：$\mathcal O(n)$。

Code

#include <cstdio>
#include <algorithm>

const int N = 1e5 + 5;

int n;
long long a[N];
char s[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    scanf("%s", s + 1);
    long long sta = 0, ans = 0, sum = 0;
    bool wat = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'G') {
            sta += a[i], ans += 5 * a[i], sum += 2 * a[i];
        }
        if (s[i] == 'W') {
            sta += a[i], ans += 3 * a[i], wat = 1;
        }
        if (s[i] == 'L') {
            sta -= a[i], ans += a[i];
            if (sta < 0) {
                ans += -sta * (wat ? 3 : 5), sta = 0;
            }
        }
        sum = std::min(sum, sta);
    }
    if (sta > 0) {
        ans -= 4 * sum / 2 + 2 * (sta - sum) / 2;
    }
    printf("%lld\n", ans);
    return 0;
}