[USACO14OPEN]公平的摄影Fair Photography

Author Avatar
ZC 11月 26, 2018
  • 在其它设备中阅读本文章

在数轴上有 $N$ 头牛,第 $i$ 头牛位于 $x_i\:(0\le x_i\le 10^9)$。没有两头牛位于同一位置。
有两种牛:白牛和花斑牛。保证至少有一头白牛。你可以把白牛涂成花斑牛,不限数量,不限哪只。
找一段尽量长的区间,使得区间的两端点均有一头牛,且区间中白牛与花斑牛的数量相等。试求区间长度。


差分,有点前缀和思想

先对输入按照P值排序,然后令W=-1 S=1,开一个F数组记录前i头牛中,白色牛减去斑点牛的数量,最后统计答案

只要区间内白色牛的数量与斑点牛的数量的差是偶数,就符合要求

#include<bits/stdc++.h>
#pragma GCC optimize(3)
namespace ZDY{
    #define res register
    #define ri res int
    #define ll long long
    #define db double
    #define sht short
    #define il inline
    #define MB template <class T> il T
    #define Fur(i,x,y) for(int i=x;i<=y;i++)
    #define fur(i,x,y) for(i=x;i<=y;i++)
    #define Fdr(i,x,y) for(int i=x;i>=y;i--)
    #define clr(x,y) memset(x,y,sizeof(x))
    #define cpy(x,y) memcpy(x,y,sizeof(x))
    #define fl(i,x) for(ri i=head[x],to;to=e[i].to,i;i=e[i].nxt)
    #define inf 21474836470
    #define fin(s) freopen(s".in","r",stdin)
    #define fout(s) freopen(s".out","w",stdin)
    #define l2(n) (ceil(log2(n)))
    //il char gc(){static char buf[1000000],*s,*t;return s==t?(((t=(s=buf)+fread(buf,1,1000000,stdin))==s)?-1:*s++) : *s++;}
    #define gc() getchar()
    il int gi(){int x=0;bool f=0;char c=gc();while(c<'0'||'9'<c){if(c=='-')f=!f;c=gc();}while('0'<=c&&c<='9'){x=x*10+c-48;c=gc();}return f?(-x):x;}
    MB ABS(T x){return x>0?x:-x;}
    MB MAX(T x,T y){return x>y?x:y;}
    MB MIN(T x,T y){return x<y?x:y;}
    MB GCD(T x,T y){return y?GCD(y,x%y):x;}
}using namespace ZDY;using namespace std;
#define N 100001
struct cow{
    int p,v;
    void in(){
        p=gi();
        char s[1];scanf("%s",s);
        v=((s[0]=='W')?-1:1);
    }
}a[N];
il bool cmp(cow x,cow y){return x.p<y.p;}
int n,b[N*4],ans=0,s;
int main(){
    n=gi();
    Fur(i,1,n)a[i].in();
    sort(a+1,a+n+1,cmp);
    clr(b,126);
    b[s=n]=a[1].p;
    Fur(i,2,n)
        s+=a[i-1].v,b[s]=MIN(b[s],a[i].p);
    Fdr(i,n*2,0)b[i]=MIN(b[i],b[i+2]);
    s=n;
    Fur(i,1,n)s+=a[i].v,ans=MAX(ans,a[i].p-b[s]);
    printf("%d\n",ans);
}