算法分析
先消环,将 $s$ 复制两遍加到 $s$ 的末尾,$a$ 也是一样
消耗牛奶的位置模式为 RL
,因为往这两个位置倒的牛奶会溢出去,然后往左右循环找 R...RL...L
模式子串左右端点。由于 $i$ 和 $i+1$ 的位置(RL)一直是满的,交换 $m$ 次后,左侧 $R$ 子串和右侧 $L$ 子串最多消耗 $m$ 升。把所有符合 R...RL...L
模式子串都找到,结果累加即可。
另外还需特判 $s$ 全为 L
以及全为 R
的情况,这两种情况显然不会消耗牛奶。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n, m;
cin >> n >> m;
string s;
cin >> s;
vector<int> a(n);
rep(i, n) cin >> a[i];
if (s == string(n, 'L') or s == string(n, 'R')) {
cout << reduce(a.begin(), a.end()) << '\n';
return 0;
}
a.insert(a.end(), a.begin(), a.end());
a.insert(a.end(), a.begin(), a.end());
s += s+s;
ll ans = 0;
rep(i, n) {
if (s[i] == 'R' and s[i+1] == 'L') {
int l = n+i, r = n+i+1;
ll sl = 0, sr = 0;
while (l and s[l-1] == 'R') --l, sl += a[l];
while (r+1 < 3*n and s[r+1] == 'L') ++r, sr += a[r];
ans += (ll)a[i] + a[i+1] + max(sl-m, 0ll) + max(sr-m, 0ll);
}
}
cout << ans << '\n';
return 0;
}