[暑假集训]Day5 T1 羊圈

时间限制: 1 Sec 内存限制: 512 MB

题目描述

ZYC的农场有N（1<=N<=100,000）块连续的区域排成一排，每块区域上都有确定数量的羊（每块区域不超过2000千只）。
现在ZYC想要将一些区域用围墙围起来，作为信息社的优秀成员，当然要给自己出点难题：他希望围起来的区域里羊的总数/区域数的值最大，并且保证围起来的区域数不小于M。

输入

第一行包括两个整数，分别表示N和M
以下N行每行一个正整数，表示对应区域羊的数量（单位千只）

输出

输出最大平均数（单位只）

样例输入

样例输出

6500

看到这道题时，我的第一个想法是打个前缀和暴力求解。于是第一份代码就出炉了。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,k;
 4 long long a[100005],sum[100005],ans;
 5 int main()
 6 {
 7     scanf("%d%d",&n,&k);
 8     for(int i=1;i<=n;i++)
 9     {
10         scanf("%lld",&a[i]);
11         a[i]*=1000;
12     } 
13     for(int i=1;i<=k;i++) sum[1]+=a[i];
14     for(int i=2;i<=n-k+1;i++) 
15     {
16         sum[i]=sum[i-1]-a[i-1]+a[i+k-1];
17     }
18     for(int i=1;i<=n-k+1;i++)
19     {
20         ans=max(ans,sum[i]/k);
21         for(int j=i+k;j<=n;j++) 
22         {
23             sum[i]+=a[j];
24             ans=max(ans,sum[i]/(j-i+1));
25         }
26     }
27     printf("%lld",ans);
28     return 0;
29 }

然而在看到了100,000的数据范围后，我就知道这种做法会T，没想到还拿了71分。数据太水了。于是我就想到了二分。其实根本就没想到。

因为前缀和具有单调性，所以我们只需要求出平均值，然后用原数列减去平均值，最后找出一个非负子序列就可以了。（题解上好像是这么说的）

下面上参考代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m;
 4 double a[100005],b[100005],sum[100005];
 5 int main()
 6 {
 7     scanf("%d%d",&n,&m);
 8     for(int i=1;i<=n;i++) scanf("%lf",&a[i]);//long long好像比double慢 
 9     double l=-1e6,r=1e6,flag=1e-8;
10     while(r-l>flag)
11     {
12         double mid=(l+r)/2;
13         for(int i=1;i<=n;i++) b[i]=a[i]-mid;//平均值减去原数列 
14         for(int i=1;i<=n;i++) sum[i]=sum[i-1]+b[i];//求一下前缀和 
15         double ans=-1e8,minn=1e8;
16         for(int i=m;i<=n;i++)
17         {
18             minn=min(minn,sum[i-m]);//不断更新左侧最小值 
19             ans=max(ans,sum[i]-minn);//找非负子序列 
20         }
21         if(ans>0) l=mid;
22         else r=mid;
23     }
24     printf("%d",int(r*1000));//按照题目要求输出 
25     return 0;
26 }