农场主 John (简称 FJ) 的农场有一长排的 N (1 <= N <= 100,000)块地组成. 每块地有一定数量 (ncows) 的牛, 1 <= ncows <=2000.
FJ 想修建环绕邻接的一组地块的栅栏, 以最大化这组地块中平均每块地中牛的个数.
这组地块必须包含至少 F (1 <= F <= N) 块地, F 作为输入给出.
给定约束, 计算出栅栏的布置情况以最大化平均数.
分析：
暴力分很好拿，只需要搞一个前缀和便可以想正解
首先我们仍可以处理出前缀和 s u m [ i ] sum[i] sum[i]表示前i个数的和
求一个字段和，可以转化为前缀和相减的形式：
m a x i − j ≥ L { A j + 1 + A j + 2 + … … + A i } = m a x { s u m i − m i n 0 ≤ j ≤ n { s u m j } } max_{i-j\geq L}\{A_{j+1}+A_{j+2}+……+A_i\}=max\{sum_i-min_{0\leq j \leq n}\{sum_j\}\} maxi−j≥L{Aj+1+Aj+2+……+Ai}=max{sumi−min0≤j≤n{sumj}}
这时我们发现每当i增加1，j的相应值也只会增加1.
根据这个性质，我们便可以舍去一层循环，直接用一个变量记录当前的最小值即可，只要与新进来的数进行比较
这样便可以 O ( n ) O(n) O(n)求出最大子段和。
由于问题具有单调性（自己思考），我们便可以用二分答案来二分平均数，将数列中每个数都减去平均数求一边最大子段和看是否>0即可
Code
#include<bits/stdc++.h> using namespace std; int n,m; double a[1011000],b[101010],summ[101010]; int main(){freopen("cowfnc.in","r",stdin);freopen("cowfnc.out","w",stdout); scanf("%d %d",&n,&m); for (int i=1;i<=n;i++) scanf("%lf",&a[i]); double k=0.00000001,l=-1000000.000,r=1000000.000; while (r-l>k){ double mid=(l+r)/double(2); for (int i=1;i<=n;i++) b[i]=a[i]-mid; for (int i=1;i<=n;i++) summ[i]=summ[i-1]+b[i]; double minn=1000000.000,ans=-10000000; for (int i=m;i<=n;i++) minn=min(minn,summ[i-m]),ans=max(ans,summ[i]-minn); if (ans>=0) l=mid; else r=mid;}printf("%d",int(r*1000));return 0; }
12345678910111213141516171819202122232425
