【BZOJ 3316】JC loves Mkk 01分数规划+单调队列

单调栈
不断吞入数据维护最值，数据具有单调性但不保证位置为其排名，同时可以按照进入顺序找出临近较值
单调队列
队列两端均可删除数据但只有队末可以加入数据，仍然不断吞入数据但同时可以额外刨除一些不符合条件的数据，强调额外刨除数据按照进入顺序，维护在有额外刨除条件下的最值，数据具有单调性但不保证位置为其排名也不保证都是合法，丧失可以按照进入顺序找出临近较值的能力

#include <cstdio>

typedef long double ld;

typedef long long ll;

const ld eps=1e-;

const int N=;

int q[N];

ld key[N<<];

int head,tail;

int n,L,R;

int a[N],ans1,ans2;

inline bool check(ld x){

    for(int i=;i<=n;++i)

        key[i]=key[i+n]=(ld)a[i]-x;

    for(int i=;i<=(n<<);++i)

        key[i]+=key[i-];

    head=,tail=;

    for(int i=L;i<=R;i+=){

        while(head<=tail&&key[q[tail]]<key[i])tail--;

        q[++tail]=i;

    }

    if(key[q[head]]>){

        ans1=,ans2=q[head];

        return true;

    }

    for(int i=;i<=n;i+=){

        while(head<=tail&&key[q[tail]]<key[i+R-])tail--;

        q[++tail]=i+R-;

        while(head<=tail&&q[head]<(i+L-))head++;

        if(key[q[head]]-key[i-]>){

            ans1=i,ans2=q[head];

            return true;

        }

    }

    head=,tail=;

    for(int i=L+;i<=R+;i+=){

        while(head<=tail&&key[q[tail]]<key[i])tail--;

        q[++tail]=i;

    }

    if(key[q[head]]-key[]>){

        ans1=,ans2=q[head];

        return true;

    }

    for(int i=;i<=n;i+=){

        while(head<=tail&&key[q[tail]]<key[i+R-])tail--;

        q[++tail]=i+R-;

        while(head<=tail&&q[head]<(i+L-))head++;

        if(key[q[head]]-key[i-]>){

            ans1=i,ans2=q[head];

            return true;

        }

    }

    return false;

}

inline ll GCD(ll x,ll y){

    return x==?y:GCD(y%x,x);

}

int main(){

    scanf("%d%d%d",&n,&L,&R),L+=L&,R-=R&;

    for(int i=;i<=n;++i)scanf("%d",&a[i]);

    for(ld l=,r=1e9,mid;l+eps<=r;mid=(l+r)/.,check(mid)?l=mid:r=mid);

    if(ans1==){printf("");return ;}

    ll s=,b=ans2-ans1+;

    for(int i=ans1;i<=ans2;++i)s+=a[i>n?i-n:i];

    ll gcd=GCD(s,b);s/=gcd,b/=gcd;

    if(b==)printf("%lld",s);

    else printf("%lld/%lld",s,b);

    return ;

}