USACO历年青铜组真题解析 | 2024年2月Milk Exchange-编程实验室

欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
希望系统学习C++/Python编程的初学者
想要提升算法与编程能力的编程爱好者

附上汇总贴：USACO历年青铜组真题解析 | 汇总-CSDN博客

【题目来源】

洛谷：[P10188 USACO24FEB] Milk Exchange B - 洛谷

【题目描述】

农夫约翰有N ( 1 ≤ N ≤ 2 ⋅ 10 5 ) N(1\le N\le 2\cdot 10^5)N(1≤N≤2⋅105)头牛排成一个圈，对于每个在1 , 2 , … , N − 1 1,2,\dots,N-11,2,…,N−1中的i ii，牛i ii的右边是牛i + 1 i+1i+1，而牛 N的右边是牛1 11。第i ii头牛有一个容量为a i ( 1 ≤ a i ≤ 10 9 ) a_i(1\le a_i\le 10^9)ai(1≤ai≤109)升的桶。所有的桶一开始都是满的。

每分钟，牛们会根据一个只由字符 ‘L’ 和 ‘R’ 组成的字符串**s 1 s 2 … s N s_1s_2\dots s_Ns1s2…sN**来交换牛奶。如果第i ii头牛至少有1 11升牛奶，它会根据s i s_isi是 ‘L’ 还是 ‘R’，分别把1 11升牛奶传给她左边或右边的牛。所有的交换都是同时发生的（也就是说，如果一头牛的桶是满的，但她给了一升牛奶同时也收到了一升牛奶，她的牛奶量是保持不变的）。如果一头牛的总牛奶量最终超过了a i a_iai，那么多出来的牛奶就会流失。

农夫约翰想知道：经过M MM分钟**( 1 ≤ M ≤ 10 9 ) (1\le M\le 10^9)(1≤M≤109)**后，所有牛中剩余的总牛奶量是多少？

【输入】

第一行包含N NN和M MM。

第二行包含一个仅由字符’L’或’R’组成的字符串**s 1 s 2 … s N s_1s_2\dots s_Ns1s2…sN**，表示每头牛会向哪个方向传递它们的牛奶。

第三行包含整数**a 1 , a 2 , … , a N a_1,a_2,\dots,a_Na1,a2,…,aN**，即每个桶的容量。

【输出】

输出一个整数，表示M分钟后所有奶牛中牛奶的总和。

请注意，此问题中涉及的大整数大小可能需要使用**64 6464**位整数数据类型（例如，在C/C++中的“long long”）。

【输入样例】

3 1 RRL 1 1 1

【输出样例】

【算法标签】

《洛谷 P10188 Milk Exchange》 #USACO# #O2优化# #2024#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intn,m;longlonga[200005],ans;string s;boolL[200005],R[200005];//L[i]=true表示点i为某个溢出结构的起点//R[i]=true表示点i为某个溢出结构的终点intmain(){cin>>n>>m;cin>>s;for(inti=0;i<n;i++){cin>>a[i];ans+=a[i];}//第一步：从左到右找出字符串s中所有的溢出结构RL，并标记其起点和终点for(inti=0;i<=n-1;i++){if(s[i]=='R'&&s[(i+1)%n]=='L'){L[i]=true;R[(i+1)%n]=true;}}//第二步：从左到右计算每个溢出结构导致的牛奶溢出for(inti=0;i<n;i++){longlongsum=0;// 每个溢出结构溢出的牛奶数量if(L[i]==true){// i号桶为某个溢出结构的起点intj=(i-1+n)%n;// 记录i号桶左边的编号jwhile(s[j]=='R'){sum+=a[j];j=(j-1+n)%n;// 继续向左}}if(R[i]==true){// i号桶为某个溢出结构的终点intj=(i+1)%n;// 记录i号桶右边的编号jwhile(s[j]=='L'){sum+=a[j];j=(j+1)%n;// 继续向右}}ans-=min(sum,(longlong)m);}cout<<ans<<endl;return0;}