【CSP：202104-2】邻域均值（Java）

题目链接

• 202104-2 邻域均值

题目描述

求解思路

• 二维前缀和：用s数组记录下二维数组a的前缀和。在进行查询时直接利用前缀和求平均值，可以降低时间复杂度。
  

• xl表示邻域的左边界，xr表示邻域的右边界，yt表示邻域的上边界，yb表示邻域的下边界。
  

• 为什么要用double类型进行比较？因为涉及除法，如果用整形的话可能会出现误差。

实现代码

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int L = in.nextInt();int r = in.nextInt();double t = in.nextDouble();int[][] a = new int[n + 1][n + 1];int[][] s = new int[n + 1][n + 1];for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {a[i][j] = in.nextInt();s[i][j] = s[i - 1][j] + s[i][j - 1] + a[i][j] - s[i - 1][j - 1];}}int cnt = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {int xl = Math.max(j - r, 1);int xr = Math.min(j + r, n);int yt = Math.max(i - r, 1);int yb = Math.min(i + r, n);double avg = (double) (s[yb][xr] - s[yb][xl - 1] - s[yt - 1][xr] + s[yt - 1][xl - 1]) /((yb - yt + 1) * (xr - xl + 1));if (avg <= t) {cnt ++;}}}System.out.println(cnt);}
}