博客地址:wmathor
题目大意是说,要求找到一个长度大于等于$F$的子段,使得这个子段内数字的平均值最大,求出这个最大值
解这道题分三步:
1. 首先二分答案,也就是平均值$mid$
2. 用原数组$A$减去平均值$mid$,得到新数组$B$,则问题转换为求$B$中是否存在一个长度大于等于$F$的子序列,使得子序列的和非负
3. 用双指针$i,j$分别指向数组$B$的前缀和数组$S$,$i$从$0$开始往后扫描,$j$永远与$i$相隔$F$长度,$i$在移动过程中不断记录最小值,然后判断$sum[j]$是否大于等于这个最小值,如果大于,说明存在一个子序列和非负
import java.util.Scanner;
public class Main {
static int[] arr = new int[100010];
static double[] sum = new double[100010];
static int n, f;
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
n = cin.nextInt();
f = cin.nextInt();
arr = new int[n + 1];
for (int i = 1; i <= n; i++)
arr[i] = cin.nextInt();
double l = 0.0, r = 2000;
double eps = 1e-5;
while (r - l > eps) {
double mid = (l + r) / 2.0;
if (check(mid))
l = mid;
else
r = mid;
}
System.out.println((int)(r * 1000));
}
static boolean check(double mid) {
for (int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + arr[i] - mid;
double min = 0;
for (int i = 0, j = f; j <= n; i++, j++) {
min = Math.min(min, sum[i]);
if (sum[j] >= min)
return true;
}
return false;
}
}