bzoj5090[lydsy11月赛]组题

裸的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;

}

巴特西

bzoj5090[lydsy11月赛]组题

最新文章

热门文章