我要招人

去企业版

首页 > 试题广场 >

小美的蛋糕切割

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

热度指数：2177 时间限制：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。

算法知识视频讲解

Java

guokexxx

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n=in.nextInt();
        long[]row=new long[n];
        int m=in.nextInt();
        long[]col=new long[m];
        int[][]matrix=new int[n][m];
        for (int i = 0; i < n; i++) {
            if (i>0) row[i]=row[i-1];
            for (int j = 0; j < m; j++) {
                matrix[i][j]=in.nextInt();
                row[i]+=matrix[i][j];
            }
        }
        long sum=row[n-1];
        for (int i = 0; i < m; i++) {
            if (i>0) col[i]=col[i-1];
            for (int j = 0; j < n; j++) {
                col[i]+=matrix[j][i];
            }
        }
        long ans=Long.MAX_VALUE;
        for (long a:row){
            ans=Math.min(ans,Math.abs(sum-a*2));
        }
        for (long a:col){
            ans=Math.min(ans,Math.abs(sum-a*2));
        }
        System.out.println(ans);
    }
}

编辑于 2024-03-21 12:28:03 回复(0)

Java

牛客509621095号

直接暴力求解，力求AC，之前直接用的int，结果有一组用例死活过不了，还以为不能暴力求解。后面改为long就好了

public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] strings = reader.readLine().split(" ");
        int n = Integer.parseInt(strings[0]);
        int m = Integer.parseInt(strings[1]);

        int[][] cake = new int[n][m];
        for (int i = 0; i < n; i++) {
            String[] s = reader.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                cake[i][j] = Integer.parseInt(s[j]);
            }
        }

        long minDiff = Long.MAX_VALUE;
        long totalSum = 0;
        for (int[] ints : cake) {
            for (long anInt : ints) {
                totalSum += anInt;
            }
        }
        long sum  = 0;
        if (cake[0].length == 1) {

            System.out.println(totalSum);
        }
        else {

            //先想象把蛋糕横着分开
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < n - i; j++) {
                    for (int k = 0; k < m; k++) {
                        sum += cake[j][k];
                    }
                }
                minDiff = Math.min(minDiff, Math.abs(sum - (totalSum - sum)));
                sum = 0;
            }
            //竖着分开的请况
            for (int i = 1; i < m; i++) {
                for (int[] ints : cake) {
                    for (int k = 0; k < m - i; k++) {
                        sum += ints[k];
                    }
                }
                minDiff = Math.min(minDiff, Math.abs(sum - (totalSum - sum)));
                sum = 0;
            }
            System.out.println(minDiff);
        }

    }

发表于 2023-08-18 00:31:29 回复(0)

提交观点

问题信息

来自：美团2023年秋招笔试...

难度：

2条回答 34收藏 1517浏览

小美的蛋糕切割

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题