题解 | #小红的蛋糕切割#

题目链接

小红的蛋糕切割

题目描述

小红拿到了一个矩形的蛋糕，共分成了 $n$ 行 $m$ 列，共 $n \times m$ 个区域，每个区域是一个小正方形，已知蛋糕每个区域都有一个美味度。

小红希望切割出一个正方形的小蛋糕（正方形边长必须平行于矩阵的边长，且必须都是完整的区域），自己吃掉正方形的部分，把剩下的部分给小紫吃。

小红希望两人吃的部分的美味度之和尽可能接近，小红吃的蛋糕美味度之和为 $x$ ，小紫吃的蛋糕美味度之和为 $y$ ，请你输出 $|x-y|$ 的最小值。

输入:

第一行输入两个正整数 $n$ 和 $m$ ，代表蛋糕区域的行数和列数
接下来 $n$ 行，每行输入 $m$ 个正整数，表示每个区域的美味度

输出:

一个整数，代表 $|x-y|$ 的最小值

解题思路

这是一个枚举问题，可以通过以下步骤解决：

预处理：
- 计算整个蛋糕的总美味度 total
- 使用二维前缀和数组加速区域和的计算
枚举策略：
- 枚举正方形的边长 len（从1到min(n,m)）
- 枚举正方形左上角的位置 (i,j)
- 计算正方形区域的美味度和剩余区域的美味度
- 更新最小差值
具体步骤：
- 构建二维前缀和数组
- 对每个可能的正方形大小和位置：
  - 计算正方形区域的美味度和
  - 计算剩余区域的美味度和
  - 计算两者差值的绝对值
  - 维护最小差值

代码

c++
java
python

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    
    // 构建二维前缀和数组
    vector<vector<ll>> sum(n + 1, vector<ll>(m + 1, 0));
    ll total = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            int x;
            cin >> x;
            total += x;
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + x;
        }
    }
    
    // 计算区域和的函数
    auto getSum = [&](int x1, int y1, int x2, int y2) -> ll {
        return sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
    };
    
    ll ans = total;
    // 枚举正方形边长
    for(int len = 1; len <= min(n, m); len++) {
        // 枚举左上角位置
        for(int i = 1; i + len - 1 <= n; i++) {
            for(int j = 1; j + len - 1 <= m; j++) {
                ll square = getSum(i, j, i + len - 1, j + len - 1);
                ll remain = total - square;
                ans = min(ans, abs(square - remain));
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        // 构建二维前缀和数组
        long[][] sum = new long[n + 1][m + 1];
        long total = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                int x = sc.nextInt();
                total += x;
                sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + x;
            }
        }
        
        long ans = total;
        // 枚举正方形边长
        for(int len = 1; len <= Math.min(n, m); len++) {
            // 枚举左上角位置
            for(int i = 1; i + len - 1 <= n; i++) {
                for(int j = 1; j + len - 1 <= m; j++) {
                    int x1 = i, y1 = j;
                    int x2 = i + len - 1, y2 = j + len - 1;
                    long square = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
                    long remain = total - square;
                    ans = Math.min(ans, Math.abs(square - remain));
                }
            }
        }
        
        System.out.println(ans);
    }
}

import sys
input=sys.stdin.readline

n, m = map(int, input().split())

# 构建二维前缀和数组
sum = [[0] * (m + 1) for _ in range(n + 1)]
total = 0
for i in range(1, n + 1):
    row = list(map(int, input().split()))
    for j in range(1, m + 1):
        total += row[j-1]
        sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + row[j-1]

def get_sum(x1, y1, x2, y2):
    return sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1]

ans = total
# 枚举正方形边长
for length in range(1, min(n, m) + 1):
    # 枚举左上角位置
    for i in range(1, n - length + 2):
        for j in range(1, m - length + 2):
            square = get_sum(i, j, i + length - 1, j + length - 1)
            remain = total - square
            ans = min(ans, abs(square - remain))

print(ans)

算法及复杂度

算法：二维前缀和 + 枚举
时间复杂度： $\mathcal{O}(n^3)$ - 需要枚举正方形的大小和位置
空间复杂度： $\mathcal{O}(n \cdot m)$ - 需要存储二维前缀和数组