美团0812算法真题解析

文章预览

来自公众号： 吴师兄学算法 题目描述 小美有一个矩形的蛋糕，共分成了n行m 列，共n*m个区域，每个区域是一个小正方形，已知蛋糕每个区域都有一个美味度。她想切一刀把蛋糕切成两部分，自己吃一部分，小团吃另一部分。 小美希望两个人吃的部分的美味度之和尽可能接近，请你输出|s1-s2|的最小值。（其中s1代表小美吃的美味度，s2代表小团吃的美味度）。 请务必保证，切下来的区域都是完整的，即不能把某个小正方形切成两个小区域。 输入描述 第一行输出两个正整数n和m，代表蛋糕区域的行数和列数。接下来的n行，每行输入m个正整数aij，用来表示每个区域的美味度。 输出描述 一个整数，代表|s1-s2|的最小值。 示例一 输入 2 3 1 1 4 5 1 4 输出 0 说明 把蛋糕像这样切开：1 1 | 4 5 1 | 4 左边蛋糕美味度之和是8 右边蛋糕美味度之和是8 所以答案是0。 ………………………………