题解 P3105 【[USACO14OPEN]Fair Photography S】

· · 题解

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

既然白牛可以变成斑点牛，那么只要一段区间[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;
}