bzoj5090 组题

题意：从长度为$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; } ```