【力扣刷题】44. 开发商购买土地-二维前缀和

Zhang, Hongxing • • ACM, Newest • 21 阅读
题目描述

在一个城市区域内，被划分成了n * m个连续的区块，每个区块都拥有不同的权值，代表着其土地价值。目前，有两家开发公司，A 公司和 B 公司，希望购买这个城市区域的土地。

现在，需要将这个城市区域的所有区块分配给 A 公司和 B 公司。

然而，由于城市规划的限制，只允许将区域按横向或纵向划分成两个子区域，而且每个子区域都必须包含一个或多个区块。 为了确保公平竞争，你需要找到一种分配方式，使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。

注意：区块不可再分。

输入描述

第一行输入两个正整数，代表 n 和 m。

接下来的 n 行，每行输出 m 个正整数。

输出描述
请输出一个整数，代表两个子区域内土地总价值之间的最小差距。
输入示例
3 3
1 2 3
2 1 3
1 2 3
输出示例
0
提示信息

如果将区域按照如下方式划分：

1 2 | 3
2 1 | 3
1 2 | 3

两个子区域内土地总价值之间的最小差距可以达到 0。

数据范围：

1 <= n, m <= 100；
n 和 m 不同时为 1。

 

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,a[110][110],x[110][110],y[110][110];
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int sum=0;
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            sum+=a[i][j];
            x[i][j]=sum;
        }
    }
    for(int j=1;j<=m;j++){
        int sum=0;
        for(int i=1;i<=n;i++){
            sum+=a[i][j];
            y[j][i]=sum;
        }
    }
    int mi=1000010;
    if(m!=1){
        for(int y=1;y<=m;y++){
            int as=0,bs=0;
            for(int i=1;i<=n;i++){
                as+=(x[i][y]-x[i][0]);
                bs+=(x[i][m]-x[i][y]);
            }
            mi=min(abs(as-bs),mi);
        }
    }
    if(n!=1){
        for(int x=1;x<=n;x++){
            int as=0,bs=0;
            for(int j=1;j<=m;j++){
                as+=(y[j][x]-y[j][0]);
                bs+=(y[j][n]-y[j][x]);
            }
            mi=min(abs(as-bs),mi);
        }
    }
    
    cout<<mi;
    return 0;
}

除此之外还可以直接用二维前缀和数组而不是分开计算x和y的前缀和数组。

公式：s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;

#include<iostream>
#include<cmath>
using namespace std;
const int N = 110;
int s[N][N];
int n, m, ans = 1e9;
void solve()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            int x;
            cin >> x;
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;
        }
    for(int i = 1; i < n; i++)
    {
        int x = abs(s[n][m] - 2 * s[i][m]);
        ans = min(ans, x);
    }
    for(int i = 1; i < m; i++)
    {
        int x = abs(s[n][m] - 2 * s[n][i]);
        ans = min(ans, x);
    }
    cout << ans;
}
int main()
{
    cin >> n >> m;
    solve();
    return 0;
}

 

版权声明：
作者：Zhang, Hongxing
链接：http://zhx.info/archives/350
来源：张鸿兴的学习历程
文章版权归作者所有，未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>
文章目录
关闭
目 录