MENU

最佳牛围栏——二分+前缀和

February 21, 2019 • Read: 2941 • 算法阅读设置

题目大意是说,要求找到一个长度大于等于$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;
    }
}
Archives Tip
QR Code for this page
Tipping QR Code