bzoj5090 组题

2018-11-01 10:36:06


题意:从长度为 $n$ 的序列中选出一段长度不小于 $m$ 的区间,使区间平均值最大,输出既约分数


这好像算是一种 $01$ 分数规划的问题?

二分一个实数答案 $k$

将序列中的数都减去 $k$

只需要看一下是否存在一个长度不小于 $m$ 的区间总和 $>0$ 就好了

维护一个前缀最小值就可以实现

得到这个区间的左右端点

再用这个区间把答案转化为既约分数就可以了

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
typedef long long ll;
const int N=1e5+5,inf=1e9;
const double eps=1e-5;
int n,m,a[N],mx=-inf,mi=inf,ansl,ansr;
double sum[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline bool check(double k)
{
    for (reg int i=1;i<=n;i++) sum[i]=sum[i-1]+1.0*a[i]-k;
    for (reg int i=m,pos=0;i<=n;i++)
    {
        if (sum[i]-sum[pos]>=eps) {ansl=pos+1,ansr=i; return 1;}
        if (sum[pos]-sum[i-m+1]>eps) pos=i-m+1;
    }
    return 0;
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int main()
{
    n=read(),m=read();
    for (reg int i=1;i<=n;i++)
    {
        a[i]=read();
        mx=max(mx,a[i]);
        mi=min(mi,a[i]);
    }
    double l=mi,r=mx; ll tot=0;
    while (r-l>eps)
    {
        double mid=(l+r)*0.5;
        if (check(mid)) l=mid; else r=mid;
    }
    int len=ansr-ansl+1;
    for (reg int i=ansl;i<=ansr;i++) tot+=a[i];
    ll d=gcd(abs(tot),len);
    printf("%lld/%lld\n",tot/d,len/d);
    return 0;
}