题解：CF1091F New Year and the Mallard Expedition

· · 题解

联考差一点就过了，出题人把 即使他处于非整数坐标时也可以 这句话删掉了导致我挂了。

首先，由于中国人能飞飞行速度比较快，而且在哪里都能飞，所以我们需要让飞过去的点尽可能的多。岩浆的点是一定只能飞过去的，其次草地能飞就飞。

所以很自然地想到贪心，先钦定最开始湖泊游过去，其余的飞过去，从后往前记录需要的体力值。

然后从前往后枚举，如果是湖泊，假设全游过去也达不到预期的体力值，就暂时全游过去，否则就通过数学推导得到经过这一段之后体力值恰好为预期体力值游泳的距离，也就是 \frac{nd+d_i-now}2，此时一定最优。

如果是岩浆，先看看体力值是否够用，不够用的话如果前面有湖泊，则先依靠折返游泳积攒体力值，没有就靠折返走路积攒体力值，体力值够了就直接飞。

如果是草地，就和湖泊差不多，甚至公式都一样，只是换成走路的时间

我们来证明一下这个贪心。首先，游泳比走路快，所以用游泳积攒体力值一定最优。其次，用折返游泳的方法换走路一定是亏的，因为这样每米会增加 2 点体力值的需求，而积攒这 2 点体力值需要 6 秒，而换掉只能省下 4 秒。然后就能发现这个贪心确实是对的。

至于我考场上怎么挂的，我特意处理了一下这个除以二，让奇数的时候走路/游泳比飞行多一，然后就挂没了。

Record

代码：

#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
int n, d[10000005], nd[10000005];
string s;
signed main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> d[i];
    cin >> s;
    s = " " + s;
    int tot = 0, sum = 0;
    string tmp = " ";
    for(int i = 1; i <= n + 1; i++){
        if(i != 1 && s[i] != s[i - 1]){
            tmp += s[i - 1];
            d[++tot] = sum;
            sum = 0;
        }
        sum += d[i];
    }
    s = tmp;
    n = tot;
    for(int i = n; i >= 1; i--){
        if(s[i] == 'W') nd[i] = max(0LL, nd[i + 1] - d[i]);
        else nd[i] = nd[i + 1] + d[i];
    }
    int e = 0, ans = 0, sump = 0, dis1 = 0, dis2 = 0;
    bool flag = 0, wk = 0; 
    for(int i = 1; i <= n; i++){
        if(s[i] == 'W'){
            if(nd[i + 1] >= e + d[i]){
                e += d[i];
                ans += 3 * d[i]; 
            }
            else{
                double swim = 1.0 * (nd[i + 1] + d[i] - e) / 2, fly = d[i] - swim;
                if(fly < 0){
                    ans += d[i] * 3;
                    e += d[i];
                    continue;
                }
                ans += nd[i + 1] + 2 * d[i] - e;
                e += nd[i + 1] - e;
            }
            flag = 1;
        }
        if(s[i] == 'G'){
            double walk = 1.0 * (nd[i + 1] + d[i] - e) / 2, fly = d[i] - walk;
            if(fly < 0){
                ans += d[i] * 5;
                e += d[i];
                continue;
            }
            ans += 2 * nd[i + 1] + 3 * d[i] - 2 * e;
            e += nd[i + 1] - e;
        }
        if(s[i] == 'L'){
            e -= d[i];
            ans += d[i];
            if(e < 0){
                if(flag){
                    dis1 += -e;
                    e = 0;
                }
                else{
                    dis2 += -e;
                    e = 0;
                }
            }
        }
    }
    ans += 3 * dis1;
    ans += 5 * dis2;
    cout << ans;
    return 0;
}