最佳牛围栏

本文主要是介绍最佳牛围栏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

title: 最佳牛围栏
date: 2023-12-17 21:26:57
tags: 二分
categories: 算法进阶指南

—> 传送门

题目大意

给定正整数序列 $A$，求一个平均数最大的、长度不小于 $L$ (连续的) 字段。

解题思路

二分答案。判定“是否存在一个长度不小于 $L$ 的字段，平均数不小于二分的值”
如果数列的每个数都减去二分的值，就转化为判定“是否存在一个长度不小于 $L$ 的字段，字段和非负”。
接下来解决两个问题：
1.求一个字段，他的和最大(无长度限制)
扫描该数列，字段和变成负数 ，则清空。
2.求一个字段，他的和最大(长度不小于 $L$)
每一次只会有一个新的取值需要进行比较，因此只需要用一个变量记录一下当前的最小值，每次新的取值与最小值比较。

单调性：答案随着某个变量增大而增大或者增大而减小。

时间复杂度

$nlogn$

实现代码

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;const int N = 6E5 + 10, mod = 1e9 + 7;double a[N],b[N],sum[N];int main()
{int N,L;cin >> N >> L;for(int i = 1;i <= N; i ++){cin >> a[i];}double l = -1e6,r = 1e6;double eps = 1e-5;while(r - eps > l){double mid = (l + r) / 2;for(int i = 1; i <= N; i ++){b[i] = a[i] - mid;}for(int i = 1; i <= N; i ++){sum[i] = (sum[i - 1] + b[i]);}double ans = -1e10;double min_val = 1e10;for(int i = L; i <= N; i ++){min_val = min(min_val,sum[i-L]);//ans = max(ans,sum[i] - min_val);}//cout << ans << endl;if(ans >= 0){l = mid;}else r = mid;}cout << int(r * 1000) << endl;return 0;
}

这篇关于最佳牛围栏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---