Codeforces 1091F New Year and the Mallard Expedition
题目链接
http://codeforces.com/contest/1091/problem/F
题目大意
有三种地形，草地、水和岩浆。Bob 可以用 $5$ 秒在草地上走一米，用 $3$ 秒在水上游一米，在任何地形上用 $1$ 秒飞一米。但是飞行每飞行一米都需要花费 $1$ $stamina$，在草地上和水上每移动一米都可以获得 $1$ $stamina$。现在 Bob 需要依次通过 $n$ 个长度分别为 $l_i$， 地形为 $s_i$ 的路径，问最小时间。注意走的不一定是整数步长。
题目分析
考虑使用贪心来做这道题。
首先考虑如何通过草地和水获得更多的 $stamina$。显然，如果要获得 $2$ $stamina$，如果是连续的水和草地，直接走完是要比在草地上走好几回在飞过草地是要值的。
因此可以这样考虑，先把所有的草地和水全部都走完，之后再验证岩浆能否飞过去再考虑是否要多走或者将走路或游泳变换成飞行。
那么先从前往后考虑，记录下现在拥有多少个 $stamina$，如果前面积攒的 $stamina$ 够用，那么就直接使用，否则，如果前面有水，那么优先在水上把需要的 $stamina$ 游出来。
这样一来，到了最后之后，可能会存在还有 $stamina$ 剩余的情况。这时候注意一点，不是所有的走路时间都是可以换成飞行的，因为可能已经在前面被某一个岩浆用掉了。显然先将走路时间换成飞行更值，因此在使用 $stamina$ 时，应当优先使用用游泳挣来的 $stamina$。这样一来，记录留下的可换的走路时间，最后将他们都换成飞行即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
int n, m, t;
char a[maxn];
long long l[maxn];
long long g = 0;
bool h = 0;
long long read(){
long long x;
scanf("%lld", &x);
return x;
}
int main(){
int i, j;
long long sum = 0;
long long ans = 0;
long long delta = 0;
n = read();
for(i=1;i<=n;i++){
l[i] = read();
}
for(i=1;i<=n;i++){
scanf(" %c", &a[i]);
if(a[i] == 'L'){
ans += l[i];
if(delta >= l[i]){
delta -= l[i];
}else{
if(h){
ans += 3ll * (l[i] - delta);
delta = 0;
}else{
ans += 5ll * (l[i] - delta);
delta = 0;
}
}
}else{
if(a[i] == 'G'){
ans += 5ll * l[i];
g += 2ll * l[i];
delta += l[i];
}else{
ans += 3ll * l[i];
h = true;
delta += l[i];
}
}
g = min(g, delta);
}
if(delta >= g){
ans -= 2ll * g;
delta -= g;
ans -= delta;
}else{
ans -= 2ll * delta;
}
printf("%lld\n", ans);
return 0;
}