小美的蛋糕切割

[编程题]小美的蛋糕切割

热度指数：904 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小美有一个矩形的蛋糕，共分成了 $n$ 行 $m$ 列，共 $n \times m$ 个区域，每个区域是一个小正方形，已知蛋糕每个区域都有一个美味度。她想切一刀把蛋糕切成两部分，自己吃一部分，小团吃另一部分。

小美希望两个人吃的部分的美味度之和尽可能接近，请你输出 $|s_1-s_2|$ 的最小值。（其中 $s_1$ 代表小美吃的美味度， $s_2$ 代表小团吃的美味度）。

请务必保证，切下来的区域都是完整的，即不能把某个小正方形切成两个小区域。

输入描述:

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

输出描述:

一个整数，代表  的最小值。

示例1

输入

2 3
1 1 4
5 1 4

输出

说明

把蛋糕像这样切开：
1 1 | 4
5 1 | 4
左边蛋糕美味度之和是8
右边蛋糕美味度之和是8
所以答案是0。

算法知识视频讲解

剑与她皆失

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long ans = (long)9e18;
        int n = sc.nextInt(), m = sc.nextInt();
        long[][] a = new long[n+5][m+5];
        long[][] b = new long[n+5][m+5];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + a[i][j];
            }
        }
        for (int i = 1; i <= n; i++) {
            ans = Math.min(ans, Math.abs(b[i][m] * 2 - b[n][m]));
        }
        for (int j = 1; j <= m; j++) {
            ans = Math.min(ans, Math.abs(b[n][j] * 2 - b[n][m]));
        }
        System.out.print(ans);
    }
}

发表于 2024-11-26 14:46:49 回复(0)