裸的01分数规划,二分答案,没了.
#include<cstdio> #include<algorithm> using namespace std; const int maxn=100005; int a[maxn]; double b[maxn]; double c[maxn]; typedef long long ll; ll gcd(ll a,ll b){ return (b==0)?a:gcd(b,a%b); } int main(){ int n,k;scanf("%d%d",&n,&k); for(int i=1;i<=n;++i)scanf("%d",a+i); double l=-1e8,r=1e8; int R=0; while(r-l>1e-5){ double mid=(l+r)/2.0; for(int i=1;i<=n;++i)b[i]=a[i]-mid; for(int i=1;i<=n;++i)b[i]+=b[i-1]; c[0]=0; for(int i=1;i<=n;++i){ c[i]=min(c[i-1],b[i]); } bool flag=false; for(int i=k;i<=n;++i){ if(c[i-k]<=b[i]){ flag=true;R=i;break; } } if(flag)l=mid; else r=mid; } double Min=0;int L=0; for(int j=1;j<=R-k;++j){ if(b[j]<Min)L=j,Min=b[j]; } ll sum=0; for(int i=L+1;i<=R;++i)sum+=a[i]; if(sum<0){ printf("-");sum=-sum; } ll g=gcd(sum,R-L); printf("%lld/%lld\n",sum/g,(R-L)/g); return 0; }转载于:https://www.cnblogs.com/liu-runda/p/8427327.html
