Descrição do problema

Em uma região urbana dividida em blocos contínuos de n x m, cada bloco possui um valor diferente representando sua valoração imobiliária. Dois desenvolvedores, Empresa A e Empresa B, desejam comprar这块区域的土地.

O objetivo é distribuir todos os blocos dessa região entre as duas empresas de forma que a diferença entre os valores totais das áreas atribuídas a cada empresa seja mínima.

Requisitos

1. A região deve ser dividida em dois sub-áreas apenas por uma divisão horizontal ou vertical.
2. Cada sub-área deve conter um ou mais blocos.
3. A diferença entre os valores totais das duas sub-áreas deve ser minimizada.

Entrada

• A primeira linha contém dois inteiros n e m, representando o número de linhas e colunas.
• As n linhas subsequentes contêm m inteiros cada, representando os valores dos blocos.

Saída

A diferença mínima entre os valores totais das duas sub-áreas.

Exemplo

Entrada:

3 3
1 2 3
2 1 3
1 2 3

Saída:

0

**Explicação:**A divisão pode ser feita da seguinte forma:

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

Os valores totais de cada sub-área são iguais, resultnado em uma diferença de 0.

Abordagem usando soma prefixal

A ideia é calcular as somas prefixais para linhas e colunas, permitindo uma divisão eficiente da matriz.

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int total = 0;
    vector<vector<int>> matriz(n, vector<int>(m, 0));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> matriz[i][j];
            total += matriz[i][j];
        }
    }

    vector<int> horizontal(n, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            horizontal[i] += matriz[i][j];
        }
    }

    vector<int> vertical(m, 0);
    for (int j = 0; j < m; j++) {
        for (int i = 0; i < n; i++) {
            vertical[j] += matriz[i][j];
        }
    }

    int min_diff = INT_MAX;
    int corteHorizontal = 0;
    for (int i = 0; i < n; i++) {
        corteHorizontal += horizontal[i];
        int diff = abs(total - 2 * corteHorizontal);
        if (diff < min_diff) {
            min_diff = diff;
        }
    }

    int corteVertical = 0;
    for (int j = 0; j < m; j++) {
        corteVertical += vertical[j];
        int diff = abs(total - 2 * corteVertical);
        if (diff < min_diff) {
            min_diff = diff;
        }
    }

    cout << min_diff << endl;
    return 0;
}

Abordagem otimizada

Esta abordagem optimiza o cálculo usando uma única passagem para acumular as somas necessárias.

#include
#include
#include

using namespace std;

int main() {
int n, m;
cin >> n >> m;
int total = 0;
vector> matriz(n, vector(m, 0));

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> matriz[i][j];
total += matriz[i][j];
}
}

int min_diff = INT_MAX;
int somaLinha = 0;

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
somaLinha += matriz[i][j];
if (j == m - 1) {
int diff = abs(total - 2 * somaLinha);
if (diff < min_diff) {
min_diff = diff;
}
}
}
somaLinha = 0;
}

int somaColuna = 0;

for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
somaColuna += matriz[i][j];
if (i == n - 1) {
int diff = abs(total - 2 * somaColuna);
if (diff < min_diff) {
min_diff = diff;
}
}
}
somaColuna = 0;
}

cout << min_diff << endl;
return 0;
}