Milk Exchange

题目描述

农夫约翰有 $N$ 头奶牛（$1 \leq N \leq 2 \cdot 10^5$）围成一个圆圈排成一列，使得对每个 $i$ 属于 $1,2,\dots,N-1$，第 $i$ 头奶牛右边的是第 $i+1$ 头奶牛，而第 $N$ 头奶牛右边的是第 $1$ 头奶牛。第 $i$ 头奶牛有一个容量为 $a_i$（$1 \leq a_i \leq 10^9$）升的桶。所有桶最初都是满的。 每一分钟，奶牛会按照一个仅由字符 $\text{‘L’}$ 和 $\text{‘R’}$ 组成的字符串 $s_1s_2\dots s_N$ 进行交换牛奶。若第 $i$ 头奶牛至少有 $1$ 升牛奶，则当 $s_i=\text{‘L’}$ 时她会向左边的奶牛传递 $1$ 升牛奶；当 $s_i=\text{‘R’}$ 时她会向右边的奶牛传递 $1$ 升牛奶。所有交换同时发生（即：如果一头奶牛的桶是满的，她送出 1 升但也收到 1 升，则她的牛奶量保持不变）。如果某头奶牛的牛奶总量曾经超过 $a_i$，则超出的牛奶会丢失。 农夫约翰想知道：经过 $M$ 分钟（$1 \leq M \leq 10^9$）后，所有奶牛剩余的牛奶总量是多少？

输入格式

第一行包含 $N$ 和 $M$。 第二行包含一个字符串 $s_1s_2\dots s_N$，仅由字符 $\text{‘L’}$ 或 $\text{‘R’}$ 组成，表示每头奶牛将把牛奶传递的方向。 第三行包含整数 $a_1, a_2, \dots, a_N$，表示每个桶的容量。

输出格式

输出一个整数，表示经过 $M$ 分钟后所有奶牛的牛奶总和。 注意：本题涉及的整数可能很大，可能需要使用 64 位整数类型（例如 C/C++ 中的 "long long"）。

3 1
RRL
1 1 1

2

5 20
LLLLL
3 3 2 3 3

14

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

38

提示

奶牛 $2$ 和 $3$ 互相传递一升牛奶，因此它们的牛奶得以保持。当奶牛 $1$ 把牛奶传给奶牛 $2$ 时，奶牛 $2$ 的桶发生溢出，一分钟后有一升牛奶丢失。 每头奶牛都向左边的奶牛传递一升牛奶，并从右边的奶牛获得一升牛奶，因此无论经过多长时间，所有牛奶都会被保留。 起初总共有 51 升牛奶。经过 5 分钟后，奶牛 $3$、$6$ 和 $7$ 将分别丢失 5、3 和 5 升牛奶。因此，总共剩余 38 升牛奶。 评分： 输入 4-8：$N,M \le 1000$ 输入 9-16：无额外限制。 题目来源：Chongtian Ma, Alex Liang

标签: USACO|2024|Bronze

来源

USACO|2024|Bronze