WA第5和第8个点
查看原帖
WA第5和第8个点
312045
uuk788009楼主2024/2/26 18:59

大体思路就是把LLLLLL和RRRRRR合为一个点,直到RL的前一个R或者后一个L,计算这个点总量sumsum,然后这个点会导致min(sum,m)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;
}
2024/2/26 18:59
加载中...