自动搬运

查看原文

来自洛谷，原作者为

	Mascros **

搬运于2025-08-24 21:45:21，当前版本为作者最后更新于2020-03-14 15:49:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前缀和记录白牛数减去斑点牛数。

既然白牛可以变成斑点牛，那么只要一段区间[l,r]内的白牛数大于等于斑点牛数且总数为偶数，即 sum[r]-sum[l-1]>=0且(sum[r]-sum[l-1])%2==0 ,使r-l最长即可。

观察发现，当某点i的前缀和sum[i]≥0时，由于sum[1]一定是1或-1，那么

若i是偶数，那么sum[i]-sum[0]一定满足条件，

若i是奇数，那么sum[i]-sum[1]一定满足条件。

当某点i的前缀和sum[i]<0时，要找到点j (j<i)使得sum[i]-sum[j]>=0,当sum[i]-sum[j]=0时一定是最优的（因为前缀和是+1-1连续的且从0开始的）

故记录该前缀和出现的第一次位置即可，这里用map记录。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
typedef long long ll;
struct node{
	ll no;
	int w;//W=1,S=-1
}a[MAXN];
ll sum[MAXN];
map<ll,int> m;
bool cmp(node x,node y)
{
	return x.no<y.no;
}
int main()
{
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	ll x;
	ll ans=0;
	char b;
	sum[0]=0;
    for(int i=1;i<=n;++i)
    {
    	cin>>x>>b;
		a[i].no=x;
        if(b=='W')
        	a[i].w=1;
        else
        	a[i].w=-1;
        
    }
    sort(a+1,a+n+1,cmp);
    m[0]=0;
    for(int i=1;i<=n;++i)
    {
		sum[i]=sum[i-1]+a[i].w;
        if(m[sum[i]]==0&&sum[i]<0)
        	m[sum[i]]=i;
		else if(sum[i]<0)
			ans=max(ans,a[i].no-a[m[sum[i]]+1].no);
		if(sum[i]%2==0&&sum[i]>=0)
			ans=max(ans,a[i].no-a[1].no);
		else if(sum[i]>=0)
			ans=max(ans,a[i].no-a[2].no);
	}
	cout<<ans;
    return 0;
}