Codeforces1091F. New Year and the Mallard Expedition

1月06

codeforces, 基础算法, 贪心

Codeforces1091F. New Year and the Mallard Expedition

题目大意

有一段分为n段的路，有草地，水和岩浆。可以在草地上走，水里游泳，任何地形上飞，走1单位消耗5单位时间，获得1点能量；游泳消耗3单位时间，获得1点能量；飞消耗1单位时间，消耗1点能量，求走完这段路的最短时间。

题解

先假设在所有草地上走，在水中游泳，在岩浆上飞。
如果某一时刻需要飞而能量不足，可以在前面的某处反复移动获得能量，如果有水优先游泳。
如果最后能量过多，就需要将前面游泳或走的一段路变成飞，但必须保证不能在某个位置能量为负。
我们应该尽可能多的将走路转化成飞，从头开始维护这个值，显然不能超过草地的长度，因为不能出现能量为负的位置，还需要用当前能量/2更新这个值。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
ll read()
{
    char ch=getchar();ll f=0,x=1;
    while(ch<'0'||ch>'9'){if(ch=='-') x=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){f=(f<<1ll)+(f<<3ll)+ch-'0';ch=getchar();}
    return f*x;
}
char s[100005];
ll a[100005];
int n;
int main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    scanf("%s",s+1);
    ll ans=0,now=0,temp=0;bool w=0;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='G')
        {
            ans+=5LL*a[i];
            now+=a[i];
            temp+=2LL*a[i];
        }
        else if(s[i]=='W')
        {
            ans+=3*a[i];
            now+=a[i];
            w=1;
        }
        else
        {
            ans+=a[i];
            now-=a[i];
            if(now<0)
            {
                ans-=now*(w?3:5);
                now=0;
            }
        }
        temp=min(temp,now);
    }
    if(now>0)
    {
        ans-=2LL*temp;
        ans-=now-temp;
    }
    cout<<ans;
}

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

ll read()

{

char ch=getchar();ll f=0,x=1;

while(ch<'0'||ch>'9'){if(ch=='-') x=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){f=(f<<1ll)+(f<<3ll)+ch-'0';ch=getchar();}

return f*x;

}

char s[100005];

ll a[100005];

int n;

int main()

{

n=read();

for(int i=1;i<=n;i++) a[i]=read();

scanf("%s",s+1);

ll ans=0,now=0,temp=0;bool w=0;

for(int i=1;i<=n;i++)

{

if(s[i]=='G')

{

ans+=5LL*a[i];

now+=a[i];

temp+=2LL*a[i];

}

else if(s[i]=='W')

{

ans+=3*a[i];

now+=a[i];

w=1;

}

else

{

ans+=a[i];

now-=a[i];

if(now<0)

{

ans-=now*(w?3:5);

now=0;

}

temp=min(temp,now);

}

if(now>0)

{

ans-=2LL*temp;

ans-=now-temp;

}

cout<<ans;

}

mengbierr