最佳牛围栏

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;
}