BZOJ3316:JC loves Mkk 分数规划+单调队列+恶心题

思路:

首先分数规划是显然的.

其次就是要求长度必须为偶数,我们可以分成两种情况讨论也可以解决.

然后对于每一次二分,我们维护一个前缀和,那么以当前位置为结尾的最大权值和所对应的开头位置的前缀和我们利用一个单调队列维护即可.

关键是输出答案时要输出一个分数或整数!这个坑死爹了.

惨不忍睹地尝试了无数种方法之后.接近崩溃.(尤其是枚举分母一点都不靠谱啊啊啊啊啊啊啊)

终于想到了一种方法,在二分的时候顺便更新答案,最后直接输出.然后就这样水过去了.

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
 
typedef long double f2;
typedef long long LL;
 
#define N 100010
int n,l,r,a[N<<1],b[N],q[N],fr,ta;
 
f2 sum[N];LL realsum[N];
 
LL gcd(LL a,LL b){return(!b)?a:gcd(b,a%b);}
 
struct Ans{
    LL x,y;
    Ans(){}
    Ans(LL _x,LL _y):x(_x),y(_y){}
    bool operator<(const Ans&B)const{return x*B.y>y*B.x;}
};
 
inline void upd(Ans&t,int l,int r){
    Ans tmp=Ans(realsum[r]-realsum[l-1],2*(r-l+1));
    if(tmp<t)t=tmp;
}
 
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    //freopen("me.out","w",stdout);
#endif
    scanf("%d%d%d",&n,&l,&r);if(l<1)l=1;if(r>n)r=n;
    register int i,j;for(i=1;i<=n;++i)scanf("%d",&a[i]);for(i=n+1;i<=2*n;++i)a[i]=a[i-n];
     
    l=l%2==0?l:l+1,l>>=1;
    r=r%2==0?r:r-1,r>>=1;
     
    f2 L,R,mid,res=0;
    Ans sav(0,1);
     
    //solve1
    for(i=1;i<=n;++i)b[i]=a[2*i-1]+a[2*i],realsum[i]=realsum[i-1]+b[i];
     
    for(L=0,R=1e9;R-L>1e-10;){
        mid=(L+R)/2;
         
        for(i=1;i<=n;++i)sum[i]=sum[i-1]+b[i]-2*mid;
         
        f2 Max=sum[l];upd(sav,1,l);
        for(fr=ta=0,i=l+1;i<=n;++i){
            if(i<=r)Max=max(Max,sum[i]),upd(sav,1,i);
            while(fr^ta&&sum[q[ta-1]]>sum[i-l])--ta;q[ta++]=i-l;
            while(fr^ta&&q[fr]<i-r)++fr;if(fr^ta)Max=max(Max,sum[i]-sum[q[fr]]),upd(sav,q[fr]+1,i);
        }
         
        if(Max>=0)L=mid;else R=mid;
    }res=max(res,L);
     
    //solve2
    for(i=1;i<n;++i)b[i]=a[2*i]+a[2*i+1];b[n]=a[2*n]+a[1];
    for(i=1;i<=n;++i)realsum[i]=realsum[i-1]+b[i];
     
    for(L=0,R=1e9;R-L>1e-10;){
        mid=(L+R)/2;
         
        for(i=1;i<=n;++i)sum[i]=sum[i-1]+b[i]-2*mid;
         
        f2 Max=sum[l];upd(sav,1,l);
        for(fr=ta=0,i=l+1;i<=n;++i){
            if(i<=r)Max=max(Max,sum[i]),upd(sav,1,i);
            while(fr^ta&&sum[q[ta-1]]>sum[i-l])--ta;q[ta++]=i-l;
            while(fr^ta&&q[fr]<i-r)++fr;if(fr^ta)Max=max(Max,sum[i]-sum[q[fr]]),upd(sav,q[fr]+1,i);
        }
     
        if(Max>=0)L=mid;else R=mid;
    }res=max(res,L);
     
     
    LL ansx=sav.x,ansy=sav.y,Gcd=gcd(ansx,ansy);ansx/=Gcd,ansy/=Gcd;
#ifndef ONLINE_JUDGE
    if(ansy==1)printf("%I64d",ansx);else printf("%I64d/%I64d",ansx,ansy);
#else
    if(ansy==1)printf("%lld",ansx);else printf("%lld/%lld",ansx,ansy);
#endif
     
    return 0;
}