最佳牛围栏

发布时间:2023年12月17日

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

—> 传送门

题目大意

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

解题思路

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

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

时间复杂度

n l o g n nlogn 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;
}
文章来源:https://blog.csdn.net/m0_73865722/article/details/135051116
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。