免费自建 响应式 网站关键词免费下载

小R的蛋糕分享

问题描述
小R手里有一个大小为 n 行 m 列的矩形蛋糕，每个小正方形区域都有一个代表美味度的整数。小R打算切割出一个正方形的小蛋糕给自己，而剩下的部分将给小S。她希望两人吃的部分的美味度之和尽量接近。
我们定义小R吃到的部分的美味度之和为 s_1，而小S吃到的部分的美味度之和为 s_2，请你帮助小R找到一个切割方案，使得 |s_1 - s_2| 的值最小。

测试样例

样例1：
输入：n = 3, m = 3, a = [[1, 2, 3], [2, 3, 4], [3, 2, 1]]
输出：1

样例2：
输入：n = 4, m = 4, a = [[1, 2, 3, 4], [4, 3, 2, 1], [1, 2, 3, 4], [4, 3, 2, 1]]
输出：2

样例3：
输入：n = 2, m = 2, a = [[5, 5], [5, 5]]
输出：10

题解

核心思想，枚举每一个点作为正方形右下角的那个点。使用前缀和数组进行重复求和运算。

#include <iostream>
#include <vector>
#include <string>using namespace std;int solution(int n, int m, vector<vector<int>>& a) {// PLEASE DO NOT MODIFY THE FUNCTION SIGNATURE// write code hereint sum = 0;// 二维前缀和，记录0,0到i,j的美味度和//int num[n][m+1];vector<vector<int>> num(n + 1, vector<int>(m + 1, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {num[i + 1][j + 1] = a[i][j] + num[i][j+1] + num[i+1][j] - num[i][j];sum += a[i][j];}}int ans = INT32_MAX;int maxNum = min(n, m);for (int i = 1; i <= maxNum; i++) {for (int r = 0; r < n; r++) {for (int c = 0; c < m; c++) {if (c + 1 < i  || r + 1 < i) {continue;}int tmp = num[r+1][c+1] - num[r+1][c+1-i] - num[r+1-i][c+1] + num[r+1-i][c+1-i];ans = min(ans, abs(sum - 2 * tmp));}}}return ans;
}