题面
核心思想
前缀和(不过是以一整行或一整列的维度)(滑动窗口应该也可以)
需要注意的是可以横着切也可以竖着切
代码
import java.util.*;
public class Main {
public static void main(String[] args) {
final long MOD = (long) (1e9 + 7);
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
long[] preSumCol = new long[m]; // 列前缀和
long[] preSumRow = new long[n]; // 行前缀和
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
int in = scanner.nextInt();
preSumCol[j] += in; // 只是当前列的值
preSumRow[i] += in; // 只是当前行的值
}
if(i > 0)
preSumRow[i] += preSumRow[i - 1]; // 计算行前缀和
}
for(int j = 1; j < m; j++) preSumCol[j] += preSumCol[j - 1]; // 计算列前缀和
// 先竖着切
// 初始值 表示在第0列的左边竖着切一刀
long res = preSumCol[m - 1];
//j表示在第j列的右边竖着切一刀
for(int j = 0; j < m; j++){
long left = preSumCol[j];
long right = preSumCol[m - 1] - preSumCol[j];
res = Math.min(res, Math.abs(left - right));
}
// 横着切 同样先是第0行的上边横着切一刀
res = Math.min(res, preSumRow[n - 1]);
// i表示在第i行的上边横着切一刀
for(int i = 0; i < n; i++){
long up = preSumRow[i];
long down = preSumRow[n - 1] - preSumRow[i];
res = Math.min(res, Math.abs(up - down));
}
System.out.println(res);
}
}
标签:真题,int,res,美团,届秋招,long,preSumRow,preSumCol,Math
From: https://www.cnblogs.com/ganyq/p/18114989