P10188 [USACO24FEB] Milk Exchange B题目描述Farmer John 的NNN1≤N≤2⋅1051\le N\le 2\cdot 10^51≤N≤2⋅105头奶牛排成一圈使得对于1,2,…,N−11,2,\ldots,N−11,2,…,N−1中的每个iii奶牛iii右边的奶牛是奶牛i1i1i1而奶牛NNN右边的奶牛是奶牛111。第iii头奶牛有一个容量为整数aia_iai​1≤ai≤1091\le a_i\le 10^91≤ai​≤109升的桶。所有桶初始时都是满的。每一分钟奶牛都会根据一个字符串s1s2…sNs_1s_2\ldots s_Ns1​s2​…sN​传递牛奶该字符串仅由字符L和R组成。当第iii头奶牛至少有111升牛奶时如果siLs_i\texttt{L}si​L她会将111升牛奶传递给她左边的奶牛如果siRs_i\texttt Rsi​R则传递给右边的奶牛。所有交换同时发生即如果一头奶牛的桶是满的送出一升牛奶但也收到一升则她的牛奶量保持不变。如果此时一头奶牛的牛奶量超过aia_iai​则多余的牛奶会损失。FJ 想要知道经过MMM分钟1≤M≤1091\le M\le 10^91≤M≤109后所有奶牛总共还余下多少牛奶输入格式输入的第一行包含NNN和MMM。第二行包含一个字符串s1s2…sNs_1s_2\ldots s_Ns1​s2​…sN​仅由字符L或R组成表示每头奶牛传递牛奶的方向。第三行包含整数a1,a2,…,aNa_1,a_2,\ldots,a_Na1​,a2​,…,aN​为每个桶的容量。输出格式输出一个整数为MMM分钟后所有奶牛总共余下的牛奶量。注意这个问题涉及到的整数可能需要使用 64 位整数型例如C/C 中的long long。输入输出样例 #1输入 #13 1 RRL 1 1 1输出 #12输入输出样例 #2输入 #25 20 LLLLL 3 3 2 3 3输出 #214输入输出样例 #3输入 #39 5 RRRLRRLLR 5 8 4 9 3 4 9 5 4输出 #338说明/提示样例解释 1奶牛222和333互相传递一升牛奶因此她们的牛奶得以保留。当奶牛111将牛奶传递给奶牛222时奶牛222的桶会溢出从而一分钟后损失了一升牛奶。样例解释 2每头奶牛都将一升牛奶传递给左边的奶牛并从右边的奶牛那里获得一升牛奶因此无论经过多长时间所有牛奶都会被保留下来。样例解释 3初始时共有515151升牛奶。555分钟后奶牛333666和777将分别损失555333和555升牛奶。因此总共还剩下383838升牛奶。测试点性质测试点4−84-84−8N,M≤1000N,M\le 1000N,M≤1000。测试点9−169-169−16没有额外限制。C实现#includebits/stdc.husingnamespacestd;typedeflonglongll;constintN2e55;ll a[N],b[N];intmain(){ios::sync_with_stdio(false);cin.tie(0);ll n,m;ll ans0,sum0;cinnm;string s;cins;ss[n-1]s;for(inti1;in;i){cina[i];suma[i];}for(inti0;in;i){if(s[i]Rs[i1]L){ll l0,r0;intlposi-10?i-1n:i-1,rposi2n?i2-n:i2;while(s[lpos]R){la[lpos];lpos--;if(lpos0)lposn;}while(s[rpos]L){ra[rpos];rpos;if(rposn)rpos-n;}ansmin(m,l)min(m,r);}}coutsum-ans;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容