最佳牛围栏
题目 最佳牛围栏
思路分析
最大平均数在0~2000之间 且具有单调性
可以用二分去找到 还是假设它为x
(一个平均数的小技巧 将原数组的值全减去平均数 可以构造出一个新的数组 方便计算)
把所有数减去这个x 因为x是最大平均数
所以肯定就剩下少数几段的和≥0 答案肯定在里面 范围一下就缩小了很多
将这个处理过的数组构造前缀和
要看某段的和是否大于等于0
就只要用s[r]-s[l-1]≥0即可
其中l和r相差F
但是这样的话就只考虑得到F块地 对于至少F的条件没满足
发现其实s[r]-s[l-1]≥0 仅仅大于0是不够的 还得结果越大越好
那要结果越大 就得s[l-1]越小
公式化成s[r]≥s[l-1]min
也就是说 如果F长度以外 存在某个值让它比F长度的s[r]≥s[l-1]更大 那它才是最优解
这样一来就考虑到了>F的情况（假设F是3 这样就考虑到了4 5 的情况）
那么肯定就需要存储这个最小值
使用minv=min(minv,s[l-1])
公式化成 s[r]≥minv
不断去取mid判断这个条件
如果满足 说明某个平均数存在 它一定是在x的左边或者等于x 让l=mid
如果不满足 说明这个平均数肯定不存在 mid取大了 答案在左边 让r=mid
因为是浮点数二分 不存在什么加一的问题
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=100010;
int n,F;
int cows[N];
double sum[N];
bool check(double mid){
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+cows[i]-mid;
double minv=0;
for(int i=1,j=F;j<=n;i++,j++){
minv=min(minv,sum[i-1]);
if(sum[j]>=minv) return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>F;
for(int i=1;i<=n;i++) cin>>cows[i];
double l=0,r=2000;
while(r-l>1e-5){
double mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
cout<<int(r*1000);
return 0;
}
💬 评论