Farmer John 的牛奶传递问题

题目描述

Farmer John 的 N（1 ≤ N ≤ 2⋅10^5）头奶牛排成一个圈，对于 1, 2, ..., N−1 中的每个 i，奶牛 i 右边的奶牛是奶牛 i+1，而奶牛 N 右边的奶牛是奶牛 1。第 i 头奶牛有一个容量为整数 ai（1 ≤ ai ≤ 10^9）升的桶。所有桶初始时都是满的。

每一分钟，奶牛会根据字符串 s1s2…sN 传递牛奶，该字符串仅由字符 ‘L’ 和 ‘R’ 组成。当第 i 头奶牛至少有 1 升牛奶时，如果 si=‘L’，她会将 1 升牛奶传递给她左边的奶牛；如果 si=‘R’ 则传递给右边的奶牛。所有交换同时发生，即，如果一头奶牛送出一升牛奶但也收到一升，则她的牛奶量保持不变。如果此时一头奶牛的牛奶量超过 ai，则多余的牛奶会损失。

FJ 想要知道：经过 M 分钟（1 ≤ M ≤ 10^9）后，所有奶牛总共还余下多少牛奶？

输入格式

输入的第一行包含两个整数 N 和 M。 第二行包含一个长度为 N 的字符串 s1s2…sN，仅由字符 ‘L’ 或 ‘R’ 组成，表示每头奶牛传递牛奶的方向。 第三行包含 N 个整数 a1, a2, …, aN，表示每个桶的容量。

输出格式

输出一个整数，为 M 分钟后所有奶牛总共余下的牛奶量。

注意：这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 "long long"）。

输入样例

9 5
RRRLRRLLR
5 8 4 9 3 4 9 5 4

38

解释： 初始时，共有 51 升牛奶。5 分钟后，奶牛 3、6 和 7 将分别损失 5、3 和 5 升牛奶。因此，总共还剩下 38 升牛奶。

测试点性质

• 测试点 4-8：N, M ≤ 1000。
• 测试点 9-16：没有额外限制。

来源

USACO真题2024-02