题意比较复杂,整理一下:
\(n\) 段,每段有两个属性:长度,地形(G,W,L)
有三种运动方式:
1.游泳:W,3m/s,+1
2.走路:G,5m/s,+1
3.飞行:G,W,L,1m/s,-1
思路:贪心
需要解决两个问题:
1、遇到L时没体力飞行
解决的方法很简单:在之前的某个地方向后游泳或走路半米,再向前半米,这样可以+1
显然,游泳比走路更优,因此我们在第一次遇到W时完成所需的所有+1
当然,如果在此之前没有遇到W,则只能走路来+1
2、最后剩下部分体力
解决的方法也很简单:尽可能的将之前的运动用飞行代替,优先代替走路
注意,代替一次将会-2,同时也不能过早的代替以防止体力耗尽的情况发生
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100006;
ll a[N];
string s;
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
cin >> s;
bool flag = 0;
ll ans = 0, k = 0, num = 0;
for (int i = 0; i < n; i++) {
if (s[i] == 'W') {
flag = 1;
k += a[i];
ans += 3 * a[i];
} else if (s[i] == 'G') {
k += a[i];
ans += 5 * a[i];
num += (a[i] << 1);
} else {
ans += a[i];
k -= a[i];
if (k < 0) {
ans -= k * (flag ? 3 : 5);
k = 0;
}
}
num = min(num, k);
}
if (k > 0) ans -= (num << 1) + (k - num);
cout << ans << endl;
return 0;
}