首页 > 编程语言 >小美的蛋糕切割(美团2024届秋招笔试第一场编程真题)

小美的蛋糕切割(美团2024届秋招笔试第一场编程真题)

时间:2024-04-04 21:57:07浏览次数:27  
标签:真题 int res 美团 届秋招 long preSumRow preSumCol Math

题面

核心思想

前缀和(不过是以一整行或一整列的维度)(滑动窗口应该也可以)
需要注意的是可以横着切也可以竖着切

代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        final long MOD = (long) (1e9 + 7);
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        long[] preSumCol = new long[m]; // 列前缀和
        long[] preSumRow = new long[n]; // 行前缀和
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                int in = scanner.nextInt();
                preSumCol[j] += in; // 只是当前列的值
                preSumRow[i] += in; // 只是当前行的值
            }
            if(i > 0)
                preSumRow[i] += preSumRow[i - 1]; // 计算行前缀和
        }
        for(int j = 1; j < m; j++) preSumCol[j] += preSumCol[j - 1]; // 计算列前缀和
        
        // 先竖着切
        // 初始值 表示在第0列的左边竖着切一刀
        long res = preSumCol[m - 1];
        //j表示在第j列的右边竖着切一刀
        for(int j = 0; j < m; j++){
            long left = preSumCol[j];
            long right = preSumCol[m - 1] - preSumCol[j];
            res = Math.min(res, Math.abs(left - right));
        }
        
        // 横着切 同样先是第0行的上边横着切一刀
        res = Math.min(res, preSumRow[n - 1]);
        // i表示在第i行的上边横着切一刀
        for(int i = 0; i < n; i++){
            long up = preSumRow[i];
            long down = preSumRow[n - 1] - preSumRow[i];
            res = Math.min(res, Math.abs(up - down));
        }


        System.out.println(res);
    }

}

标签:真题,int,res,美团,届秋招,long,preSumRow,preSumCol,Math
From: https://www.cnblogs.com/ganyq/p/18114989

相关文章