bzoj5090 组题

2018-11-01 10:36:06

#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];
{
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()
{
for (reg int i=1;i<=n;i++)
{
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;
}
• star
首页