安徽建设厅网站首页,网站开发aichengkeji,南京三大软件外包公司,上海金山网站建设公司AcWing 5539. 牛奶交换
Week 3 3月6日
题目描述
农夫约翰的 N N N 头奶牛排成一圈#xff0c;使得对于 1 , 2 , … , N − 1 1,2,…,N−1 1,2,…,N−1 中的每个 i i i#xff0c;奶牛 i i i 右边的奶牛是奶牛 i 1 i1 i1#xff0c;而奶牛 N N N 右边的奶牛是奶牛 …
AcWing 5539. 牛奶交换
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 i1 i1而奶牛 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 s1s2…sN 传递牛奶该字符串仅由字符 L 和 R 组成。
当第 i i i 头奶牛至少有 1 1 1 升牛奶时如果 s i s_i siL她会将 1 1 1 升牛奶传递给她左边的奶牛如果 s i s_i siR她会将 1 1 1 升牛奶传递给右边的奶牛。
所有交换同时发生即如果一头奶牛的桶是满的送出 1 1 1 升牛奶的同时也收到 1 1 1 升牛奶则她的牛奶量保持不变。
如果此时一头奶牛的牛奶量超过了桶的容量 a i a_i ai则多余的牛奶会损失。
农夫约翰想要知道经过 M M M 分钟后所有奶牛总共还余下多少牛奶
输入格式
输入的第一行包含 N N N 和 M M M。
第二行包含一个字符串 s 1 s 2 … s N s_1s_2…s_N s1s2…sN仅由字符 L 或 R 组成表示每头奶牛传递牛奶的方向。
第三行包含整数 a 1 , a 2 , … , a N a_1,a_2,…,a_N a1,a2,…,aN为每个桶的容量。
输出格式
输出一个整数为 M M M 分钟后所有奶牛总共余下的牛奶量。
数据范围 1 ≤ N ≤ 2 × 1 0 5 1 \le N \le 2 \times 10^5 1≤N≤2×105, 1 ≤ M ≤ 1 0 9 1 \le M \le 10^9 1≤M≤109, 1 ≤ a i ≤ 1 0 9 1 \le a_i \le 10^9 1≤ai≤109
输入样例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 如果有更多问题或需要进一步的帮助可以在评论区留言讨论哦 如果喜欢的话请给博主点个关注 谢谢
