大体思路就是把LLLLLL和RRRRRR合为一个点,直到RL的前一个R或者后一个L,计算这个点总量sum,然后这个点会导致min(sum,m)牛奶流失
开头和结尾特殊处理
#include<bits/stdc++.h>
#define lst(x) x==1?n:x-1
#define nxt(x) x==n?1:x+1
using namespace std;
typedef long long LL;
const int N=2e5+1;
int n,m,a[N],st,ed;
string s;
LL sum,lost,csum;
int main(){
scanf("%d%d",&n,&m);
st=0,ed=n-1;
cin>>s;
for(int i=0;i<n;++i) scanf("%d",&a[i]),sum+=a[i];
if(s[0]==s[n-1]){
int i=0,j=n-1;
while(i<n and s[i]==s[0]) csum+=a[i],++i;
if(i==n){
printf("%d\n",sum);
return 0;
}
while(j>=0 and s[j]==s[0]) csum+=a[j],--j;
if(s[0]=='R') csum-=a[i-1],++i; //RRRL...LRRR
else csum-=a[j+1],--j; //LLLR...RLLL
sum-=csum<m?csum:m;
st=i,ed=j;
csum=0;
}
else if(s[0]=='L' and s[n-1]=='R') st=1,ed=n-2; //LL...RR LR...LR LL...LR
for(int i=st;i<ed;++i){
if(s[i]==s[i+1]) csum+=a[i];
else if(s[i]=='R' and s[i+1]=='L')
sum-=csum<m?csum:m,
csum=0,
++i;
else
csum+=a[i],
sum-=csum<m?csum:m,
csum=0;
}
if(s[ed]==s[ed-1]) csum+=a[ed];
if(csum) sum-=csum<m?csum:m; //RR...LL RL...RL RL...LL
printf("%lld\n",sum);
return 0;
}