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

2024-01-10 11:33:12

题目分析:切蛋糕问题切记可以横着切,也可以竖着切。本题目需要快速求得两个矩形的和,可以用二维前缀和数组解决。然后枚举一刀切的位置。

#include <iostream>
#include <algorithm>
using namespace std;
int a[1005][1005];
long long sum[1005][1005];/**< 注意到数据范围可能超过int */
int main()
{
    int i,j,n,m;
    cin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++){
            cin>>a[i][j];/**< 二维前缀和数组常见求法 */
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
        }
    long long ans=sum[n][m];
    /**< 枚举蛋糕切割,注意可以横着也可以竖着切 */
    for(i=1;i<n;i++)
        ans=min(ans,abs(sum[i][m]-(sum[n][m]-sum[i][m])));/**<sum[i][m]上半块蛋糕  */
    for(j=1;j<m;j++)
        ans=min(ans,abs(sum[n][j]-(sum[n][m]-sum[n][j])));/**<sum[n][j]左半块蛋糕  */
    cout<<ans;
    return 0;
}

解释下:sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];作用

文章来源:https://blog.csdn.net/sigd/article/details/135498133
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。