Milk Exchange (USACO Bronze 2024 February)
一堆牛围成一个圈,每头牛根据自己的字符(L或R)每分钟向左或向右传递一升牛奶,溢出的消失。在所有桶(容量)开始都满的情况下,问过了M分钟后,一共剩下多少牛奶。
换句话说,就是问过了M分钟后,一共溢出丢失了多少升牛奶。
一些简单的情况:
LLLLL
这样的全部方向一样的情况,传递过程中不会有牛奶溢出,因为每头牛每分钟上都空出一升空间,刚好放下邻居传递过来的牛奶。RRL
经过一分钟,会丢失一升牛奶,之后牛2和牛3就一直在交换牛奶,不会再溢出。
经过模式的搜索之后,我们最终会发现:"RL"这个pattern是一个分界线
- 这两桶自己的牛奶不会有变化。
- 同时这两个桶也不会接收新的牛奶,所以"RL"和"RL"之间的牛奶(一定是
L*R*
这个正则表达式regular expression,*
表示0个或多个前面字母,所以就是LLRR, LLLR, RRR这样的pattern), 会随着时间逐步减少。 - 减少的量就是min(t, suml) + min(t, sumr),其中suml和sumr是上面的
L*R*
正则表达式中"L"和"R"的牛奶总量。
所以具体算法就是找到所有的“RL”,然后计算“RL”之间(不含”RL“自身)的suml和sumr,然后按以上公式计算t时间时的溢出量,就可以了。。
#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
int n, t;
char s[200005];
int a[200005];
long long ans, suml, sumr;
int main() {
scanf("%d %d %s", &n, &t, s);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
ans += a[i];
}
int st = -1; // pos at "RL"
for (int i = 0; i < n; i++) { // find first "RL"
if (s[i] == 'R' && s[(i+1) % n] == 'L') {
st = i;
break;
}
}
if (st == -1) {
printf("%lld", ans);
return 0;
}
ans = 0;
int i = st;
do {
ans += a[i] + a[(i+1)%n];
i = (i + 2) % n; // skip "RL"
suml = sumr = 0;
for (;;i = (i+1)%n) {
if (s[i] == 'R' && s[(i+1)%n] == 'L')
break;
if (s[i] == 'L') suml += a[i];
else sumr += a[i];
}
if (suml > t)
ans += suml-t;
if (sumr > t)
ans += sumr-t;
if (i == st)
break;
} while (i != st);
printf("%lld", ans);
return 0;
}