思路：二维前缀和+二分

这个问题其实就是在求一个靠近 $\frac{sum}{2}$ 的最近的数，不过这个数是由正方形中的数的和组成的。

那么可以考虑枚举正方形的左上角端点，然后二分正方形的边长，找到一个正方形数之和大于等于 $\frac{sum}{2}$ 的最小边长。

而这里判断时需要快速求出一个正方形内数的和，可以通过预处理二维前缀和，然后查询可以$O(1)$计算出。

时间复杂度：$O(nmlogn)$

代码

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1010;
ll pre[N][N];
int n, m;

ll get(int a, int b, int c, int d) {
    return pre[c][d] - pre[c][b - 1] - pre[a - 1][d] + pre[a - 1][b - 1];
}

ll myabs(ll a) {
    if (a >= 0) return a;
    return -a;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int x; scanf("%d", &x);
            pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + x;
        }

    ll sum = pre[n][m];
    ll half = (sum + 1) / 2;

    ll ans = sum;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            // 正方形左上角为 (i, j)

            int l = 1, r = min(n - i + 1, m - j + 1);

            // 找到大于等于 half 的最小的边长
            while (l < r) {
                int mid = (l + r) >> 1;
                if (get(i, j, i + mid - 1, j + mid - 1) >= half) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }


            ans = min(ans, myabs(sum - 2ll * get(i, j, i + l - 1, j + l - 1)));
            if (l > 1) {
                l -= 1;
                ans = min(ans, myabs(sum - 2ll * get(i, j, i + l - 1, j + l - 1)));
            }
        }

    cout << ans << "\n";

    return 0;
}

Java

import java.util.*;
public class Main{
        static int N = 1010;
    static long[][] g = new long[N][N];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                g[i][j] = in.nextInt();
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                g[i][j] += g[i-1][j] + g[i][j-1] - g[i-1][j-1];
            }
        }

        long sum = g[n][m];
        long half = (sum + 1) / 2;
        long ans = sum;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int l = 1, r = Math.min(n - i + 1, m - j + 1);
                while(l < r) {
                    int mid = l + ((r - l) >> 1 );
                    if(get(i, j, i + mid - 1, j + mid - 1) >= half){
                        r = mid;
                    }else {
                        l=mid + 1;
                    }
                }

                ans = Math.min(ans, myabs(sum - 2 * get(i, j, i + l - 1, j + l - 1)));
                if (l > 1) {
                    l -= 1;
                    ans = Math.min(ans, myabs(sum - 2 * get(i, j, i + l - 1, j + l - 1)));
                }
            }
        }
        System.out.println(ans  );

    }

    private static long myabs(long x) {
        return Math.abs(x);
    }

    private static long get(int a, int b, int c, int d) {
        return g[c][d] - g[c][b-1] - g[a-1][d] + g[a-1][b-1];
    }
}

Python

import sys
from collections import *
from functools import *

n,m=list(map(int,sys.stdin.readline().strip().split()))

mat=[]
for i in range(n):
    mat.append(list(map(int,sys.stdin.readline().strip().split())))
target=sum(sum(i) for i in mat)/2

summ=[[0]*(m+1) for i in range(n+1)]
for i in range(n):
    for j in range(m):
        summ[i+1][j+1]=mat[i][j]+summ[i][j+1]+summ[i+1][j]-summ[i][j]

minn=10**14

def check(mid):
    return (summ[i+1][j+1]-summ[i+1-mid][j+1]-summ[i+1][j+1-mid]+summ[i+1-mid][j+1-mid])<=target

def get(i1,j1,i2,j2):
    return summ[i2+1][j2+1]-summ[i1][j2+1]-summ[i2+1][j1]+summ[i1][j1]

for i in range(n):
    for j in range(m):

        left,right=0,min(i+1,j+1)
        while left<=right:
            mid=(left+right)//2
            if check(mid):
                left=mid+1
            else:
                right=mid-1
        
        minn=min(minn,abs(target-get(i-right+1,j-right+1,i,j)),abs(target-get(i-right,j-right,i,j)) if i-right>=0 else 10**12)

print(int(minn*2))

题目描述

先前，小红有一个数组，要求这个数组中选择若干个数，使得选出的数之和与剩下的数之和的差值绝对值尽可能小。

现在，问题升级了，小红有一个 $n\times m$ 的矩阵，要求从这个矩阵中选择出一个正方形，使得正方形中的数之和与剩下的数之和的差值绝对值尽可能小。

你能帮帮小红吗？

输入描述

第一行，两个正整数 $n$ 和 $m(1\leq n,m\leq 1000)$ ，表示矩阵的行数和列数

接下来的 $n$ 行，每行有 $m$ 个正整数，第 $i$ 行的第 $j$ 个正整数为 $a_{i,j}(1\leq a_{i,j}\leq 10000)$

输出描述

一个整数，表示正方形中的数之和与剩下的数之和的差值绝对值的最小值。

样例

输入

3 3
9 9 8 
2 4 4
3 5 3

输出

1

说明

选择 a[1][1], a[1][2], a[2][1], a[2][2] 构成的长度为 $2$ 的正方形，这些数和为 $24$ ，剩下的数和为 $23$ ，此时差值绝对值最小，为 $1$ 。