论坛网站备案流程图百度怎么优化网站排名

AcWing 5539. 牛奶交换

Week 3
3月6日

题目描述

农夫约翰的 $N$ 头奶牛排成一圈，使得对于 $1,2,\dots ,N-1$ 中的每个 $i$，奶牛 $i$ 右边的奶牛是奶牛 $i+1$，而奶牛 $N$ 右边的奶牛是奶牛 $1$。

第 $i$ 头奶牛有一个容量为整数 $a\_i$ 升的桶。

所有桶初始时都装满了牛奶。

每一分钟，奶牛都会根据一个字符串 $s_1{s}_2\dots s_N$ 传递牛奶，该字符串仅由字符 L 和 R 组成。

当第 $i$ 头奶牛至少有 $1$ 升牛奶时，如果 $s_i=$L，她会将 $1$ 升牛奶传递给她左边的奶牛，如果 $s_i=$R，她会将 $1$ 升牛奶传递给右边的奶牛。

所有交换同时发生（即，如果一头奶牛的桶是满的，送出 $1$ 升牛奶的同时，也收到 $1$ 升牛奶，则她的牛奶量保持不变）。

如果此时一头奶牛的牛奶量超过了桶的容量 $a_i$，则多余的牛奶会损失。

农夫约翰想要知道：经过 $M$ 分钟后，所有奶牛总共还余下多少牛奶？

输入格式

输入的第一行包含 $N$ 和 $M$。

第二行包含一个字符串 $s_1{s}_2\dots s_N$，仅由字符 L 或 R 组成，表示每头奶牛传递牛奶的方向。

第三行包含整数 $a_1,a_2,\dots ,a_N$，为每个桶的容量。

输出格式

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

数据范围

$1\le N\le 2\times 10^5$,
$1\le M\le 10^9$,
$1\le a_i\le 10^9$

输入样例1：

3 1
RRL
1 1 1

输出样例1：

2

样例1解释

奶牛 $2$ 和 $3$ 互相传递一升牛奶，因此她们的牛奶得以保留。

当奶牛 $1$ 将牛奶传递给奶牛 $2$ 时，奶牛 $2$ 的桶会溢出，从而一分钟后损失了一升牛奶。

输入样例2：

5 20
LLLLL
3 3 2 3 3

输出样例2：

14

样例2解释

每头奶牛都将一升牛奶传递给左边的奶牛，并从右边的奶牛那里获得一升牛奶，因此无论经过多长时间所有牛奶都会被保留下来。

输入样例3：

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

输出样例3：

38

样例3解释

初始时，共有 $51$ 升牛奶。

$5$ 分钟后，奶牛 $3$，$6$ 和 $7$ 将分别损失 $5$，$3$ 和 $5$ 升牛奶。

因此，总共还剩下 $38$ 升牛奶。

---

模拟

---

AC _code

n, m = map(int, input().split())  
s = input()  
s += s  
a = list(map(int, input().split()))  
ans = sum(a)  
a += a  
# 找到第一个不连续的位置  
k = 0  
while k < n and s[k] == s[k + 1]:  k += 1  
if k < n:  i = k + 1  while i <= n:  res = 0  j = i  while j <= k + n and s[j] == s[i]:  res += a[j]  j += 1  if s[i] == 'R':  res -= a[j - 1]  else:  res -= a[i]  ans -= min(m, res)  i = j  
print(ans)

---

END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢