Tóm tắt đề bài

Cho một lưới ô vuông kích thước \(m \times n\). Có \(k\) chuyến xe đổ đất vào các ô \((x_i, y_i)\) với khối lượng \(a_i\). Tổng khối lượng đất đá chia hết cho \(m \times n\). Cần san đều lượng đất đá này sao cho mỗi ô trong lưới có lượng đất bằng nhau. Chi phí để di chuyển 1 tấn đất giữa hai ô kề cạnh là 1. Tìm chi phí tối thiểu để thực hiện việc san lấp này.

Phân tích

• Kích thước: \(m, n, k \leq 10^6\). Tổng khối lượng đất lên tới \(10^{12}\).
• Mục tiêu: Sau khi san lấp, mỗi ô sẽ có lượng đất là \(avg = \frac{\sum a_i}{m \times n}\).
• Khoảng cách Manhattan: Chi phí di chuyển đất từ ô \((x_1, y_1)\) đến ô \((x_2, y_2)\) thực chất là khoảng cách Manhattan: \(|x_1 - x_2| + |y_1 - y_2|\).
• Tính độc lập: Một quan sát quan trọng trong các bài toán di chuyển trên lưới với chi phí Manhattan là ta có thể tách biệt việc di chuyển theo hàng và di chuyển theo cột.
  • Việc di chuyển đất để các hàng có tổng lượng đất bằng nhau (mỗi hàng có \(n \times avg\) tấn).
  • Việc di chuyển đất để các cột có tổng lượng đất bằng nhau (mỗi cột có \(m \times avg\) tấn).
  • Tổng chi phí tối thiểu sẽ là tổng chi phí tối thiểu của hai bài toán 1 chiều này.

Hướng giải quyết

1. Bài toán 1 chiều (San bằng trên một dãy)

Giả sử ta có một dãy \(A\) gồm \(L\) phần tử, mỗi phần tử \(A_i\) cần đạt được giá trị mục tiêu \(T\). Chi phí để chuyển 1 đơn vị từ \(A_i\) sang \(A_{i+1}\) (hoặc ngược lại) là 1.
Để phần tử \(A_1\) đạt được \(T\), nó phải nhận từ hoặc chuyển cho \(A_2\) một lượng là \(|A_1 - T|\). Sau đó, \(A_2\) sẽ có lượng đất mới và tiếp tục xử lý với \(A_3\).
Công thức tổng quát cho chi phí trên dãy là:

2. Áp dụng vào bài toán 2 chiều

• Bước 1: Tính tổng lượng đất của từng hàng \(row\_sum[i]\) và từng cột \(col\_sum[j]\).
• Bước 2: Tính giá trị trung bình mỗi ô \(avg = \frac{\text{total\_sum}}{m \times n}\).
• Bước 3: Tính chi phí di chuyển theo hàng:
  • Mục tiêu mỗi hàng cần có: \(target\_row = n \times avg\).
  • Chi phí hàng: \(\sum_{i=1}^{m-1} |\sum_{k=1}^{i} row\_sum[k] - i \times target\_row|\).
• Bước 4: Tính chi phí di chuyển theo cột:
  • Mục tiêu mỗi cột cần có: \(target\_col = m \times avg\).
  • Chi phí cột: \(\sum_{j=1}^{n-1} |\sum_{k=1}^{j} col\_sum[k] - j \times target\_col|\).
• Bước 5: Tổng chi phí = Chi phí hàng + Chi phí cột.

Độ phức tạp

• Thời gian: \(O(k + m + n)\) để đọc dữ liệu, tính tổng hàng/cột và tính toán chi phí. Với \(m, n, k \leq 10^6\), thuật toán này hoàn toàn đáp ứng thời gian yêu cầu.
• Bộ nhớ: \(O(m + n)\) để lưu trữ mảng tổng hàng và tổng cột.

Code tham khảo

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // Tối ưu tốc độ nhập xuất
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long m, n, k;
    if (!(cin >> m >> n >> k)) return 0;

    // Sử dụng vector để lưu tổng đất của từng hàng và từng cột
    vector<long long> row_sum(m + 1, 0);
    vector<long long> col_sum(n + 1, 0);
    long long total_sum = 0;

    for (int i = 0; i < k; ++i) {
        long long x, y, a;
        cin >> x >> y >> a;
        row_sum[x] += a;
        col_sum[y] += a;
        total_sum += a;
    }

    // Lượng đất trung bình mỗi ô
    long long avg = total_sum / (m * n);
    long long total_cost = 0;

    // Tính chi phí di chuyển theo chiều dọc (để các hàng cân bằng)
    long long target_per_row = n * avg;
    long long current_prefix_row = 0;
    for (int i = 1; i < m; ++i) {
        current_prefix_row += row_sum[i];
        // Chi phí là độ lệch giữa lượng đất hiện có và lượng đất cần có của i hàng đầu tiên
        total_cost += abs(current_prefix_row - i * target_per_row);
    }

    // Tính chi phí di chuyển theo chiều ngang (để các cột cân bằng)
    long long target_per_col = m * avg;
    long long current_prefix_col = 0;
    for (int j = 1; j < n; ++j) {
        current_prefix_col += col_sum[j];
        // Chi phí là độ lệch giữa lượng đất hiện có và lượng đất cần có của j cột đầu tiên
        total_cost += abs(current_prefix_col - j * target_per_col);
    }

    cout << total_cost << endl;

    return 0;
}