AcWing 102. 最佳牛围栏
原题链接
简单
作者:
robot
,
2021-05-08 22:40:43
,
所有人可见
,
阅读 376
将所有连续区间按右端点分为n个集合,以1结尾,以2结尾,...以n结尾。
找出(s[k] - s[i-1])/(k-i+1)最大的值; // k为某集合的右端点。
直接找不好找,可以暴力二重循环,但时间复杂度太高。
考虑将原始序列 a1 a2 ... an 分别减去 agv 变为 b1 b2 ... bn
对b序列做前缀和,则如果S[k] - S[i-1] >= 0, 则说明ai + ... + a[k]的平均值大于等于agv
若要使 S[k] - S[i-1]最大, 则使S[i-1]最小,枚举右端点时,顺便保存S[0~i-1]的最小值。
从另一个方面考虑这样做的正确性:
原始序列的前缀和s[i]表达的是前i个数之和。
那么如果 s[i] - i*agv >= 0, 则s[i]的平均值大于等于agv
对于任意区间有: (s[k] - s[i-1]) - (k-(i-1)) * agv >= 0
s[k] - k*agv - (s[i-1] - (i-1)*agv) >= 0
所以不必每次都求一个新的前缀和数组
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5;
int n, F;
double s[N];
int check(double agv)
{
double mins = 1e8, mini;
for(int i = 0, j = F; j <= n; j++,i++)
{
if(mins >= s[i] - i*agv)
{
mins = s[i] - i*agv;
mini = i;
}
if((s[j] - j*agv - mins) >= 0)
{
return true;
}
}
return false;
}
int main()
{
cin>>n>>F;
double l = 0, r = 0;
for(int i = 1; i <= n; i++)
{
cin>>s[i];
r = max(r, s[i]);
s[i] += s[i-1];
}
while(abs(r - l) > 1e-5)
{
double mid = (l + r) / 2;
//cout<<mid<<endl;
if(check(mid))
l = mid;
else r = mid;
}
cout<<int(r*1000);
return 0;
}