算法分析
(前缀和+二分)
类似于“最大值最小”、”平均数最大”的问题,一般使用二分法对该值进行判定
- 1、该问题等价于:给定正整数列
A
,求一个平均数最大的、长度不小于L
的(连续的)子段的平均数最大值 -
2、通过二分给定一个平均数,如果把数列中每个数都减去平均数得到数组
B[]
,就转换为判定“是否存在一个长度不小于L
的子段,子段和非负” -
3、上述问题中,需要对B[]数组进行前缀和
sun[]
,[i,j]
表示长度为L的区间,minv
表示sum[i]
的最小值(该最小值的位置和j
位置的距离一定大于等于L
),通过j
枚举整个数组B[]
,若sum[j] - minv >= 0
则表示存在该平均数使得该平均数满足题目条件,返回ture
,否则返回false
时间复杂度 $O(n*log2(2000))$
参考y总进阶指南的视频讲解
Java 代码
import java.util.Scanner;
public class Main {
static double[] sum = new double[100010];
static int[] cow = new int[100010];
static int n;
static int f;
//输入一个平均值,判断是否 存在一个平均值比avg大且长度不小于F的子段
public static boolean check(double avg)
{
//计算与平均数差值的平均和
for(int i = 1;i <= n;i++) sum[i] = sum[i - 1] + cow[i] - avg;
//记录到i位置前缀和最小值
double minv = 0;
for(int i = 0,j = f;j <= n;i++,j++)
{
//保证长度一定不小于F
minv = Math.min(minv, sum[i]);
if(sum[j] - minv >= 0) return true;
}
return false;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
f = scan.nextInt();
for(int i = 1;i <= n;i++) cow[i] = scan.nextInt();
double l = 0,r = 2000;
while(r - l > 1e-5)
{
double mid = (l + r)/2;
if(check(mid)) l = mid;
else r = mid;
}
System.out.println((int)(r * 1000));
}
}
有什么最大值最小的题目吗
算法分析第一点 怎么感觉我读不通顺呢
大佬 请问这道题为什么结果是r1000 而不是l1000
如果答案是整数,用
L
的话因为是下取整的原因会导致答案会少1
。谢谢大佬