【蓝桥杯集训·每日一题2025】 AcWing 5539. 牛奶交换 python

Week 3 3月6日

题目描述

农夫约翰的 N N N 头奶牛排成一圈，使得对于 1 , 2 , … , N − 1 1,2,…,N−1 1 , 2 , … , N − 1 中的每个 i i i ，奶牛 i i i 右边的奶牛是奶牛 i + 1 i+1 i + 1 ，而奶牛 N N N 右边的奶牛是奶牛 1 1 1 。 第 i i i 头奶牛有一个容量为整数 a _ i a\_i a _ i 升的桶。 所有桶初始时都装满了牛奶。 每一分钟，奶牛都会根据一个字符串 s 1 s 2 … s N s_1s_2…s_N s 1 ​ s 2 ​ … s N ​ 传递牛奶，该字符串仅由字符 L 和 R 组成。 当第 i i i 头奶牛至少有 1 1 1 升牛奶时，如果 s i

s_i= s i ​

L ，她会将 1 1 1 升牛奶传递给她左边的奶牛，如果 s i

s_i= s i ​

R ，她会将 1 1 1 升牛奶传递给右边的奶牛。 所有交换同时发生（即，如果一头奶牛的桶是满的，送出 1 1 1 升牛奶的同时，也收到 1 1 1 升牛奶，则她的牛奶量保持不变）。 如果此时一头奶牛的牛奶量超过了桶的容量 a i a_i a i ​ ，则多余的牛奶会损失。 农夫约翰想要知道：经过 M M M 分钟后，所有奶牛总共还余下多少牛奶？

输入格式

输入的第一行包含 N N N 和 M M M 。 第二行包含一个字符串 s 1 s 2 … s N s_1s_2…s_N s 1 ​ s 2 ​ … s N ​ ，仅由字符 L 或 R 组成，表示每头奶牛传递牛奶的方向。 第三行包含整数 a 1 , a 2 , … , a N a_1,a_2,…,a_N a 1 ​ , a 2 ​ , … , a N ​ ，为每个桶的容量。

输出格式

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

数据范围

1 ≤ N ≤ 2 × 1 0 5 1 \le N \le 2 \times 10^5 1 ≤ N ≤ 2 × 1 0 5 , 1 ≤ M ≤ 1 0 9 1 \le M \le 10^9 1 ≤ M ≤ 1 0 9 , 1 ≤ a i ≤ 1 0 9 1 \le a_i \le 10^9 1 ≤ a i ​ ≤ 1 0 9

输入样例1：

3 1
RRL
1 1 1

输出样例1：

2

样例1解释

奶牛 2 2 2 和 3 3 3 互相传递一升牛奶，因此她们的牛奶得以保留。 当奶牛 1 1 1 将牛奶传递给奶牛 2 2 2 时，奶牛 2 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 51 51 升牛奶。 5 5 5 分钟后，奶牛 3 3 3 ， 6 6 6 和 7 7 7 将分别损失 5 5 5 ， 3 3 3 和 5 5 5 升牛奶。 因此，总共还剩下 38 38 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 如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！ 如果喜欢的话，请给博主点个关注 谢谢