Hướng Dẫn Giải Bài 26: TỔNG CÁC SỐ ÂM TRONG BẢNG (TSA.CPP)

1. Đề bài tóm tắt

Cho một bảng số gồm ~m~ hàng và ~n~ cột (~1 \le m, n \le 1000~). Hãy tìm và tính tổng của tất cả các số có giá trị nhỏ hơn 0 (số âm) xuất hiện trong bảng.

• Đầu vào (INPUT):

  • Dòng 1: Hai số nguyên dương ~m~ và ~n~.
  • ~m~ dòng tiếp theo: Mỗi dòng chứa ~n~ số nguyên mô tả bảng số.

• Đầu ra (OUTPUT):

  • In ra một số nguyên duy nhất là tổng của các số âm tìm được.

2. Phân tích bài toán

• Khai báo mảng 2 chiều tĩnh a[1005][1005] để lưu trữ các phần tử của bảng số.
• Sử dụng 2 vòng lặp lồng nhau với chỉ số bắt đầu từ ~1~ đến ~m~ (cho hàng) và từ ~1~ đến ~n~ (cho cột) để nhập dữ liệu.
• Dùng một biến tong (khởi tạo bằng 0) để cộng dồn các giá trị âm.
• Với mỗi phần tử a[i][j], nếu a[i][j] < 0 thì cộng giá trị đó vào tong.
• Lưu ý: Biến tong nên dùng kiểu long long để phòng trường hợp tổng các số âm vượt quá giới hạn của kiểu int.

3. Độ phức tạp

• Thời gian (Time Complexity): ~O(m \times n)~ — Duyệt qua các phần tử của bảng gồm ~m~ hàng và ~n~ cột.
• Không gian (Space Complexity): ~O(m \times n)~ — Sử dụng mảng 2 chiều tĩnh kích thước tối đa ~1005 \times 1005~.

4. Mã nguồn C++ minh họa

#include <bits/stdc++.h>
using namespace std;

// Khai bao mang 2 chieu tinh kich thuoc toi da (chi so tu 1)
int a[1005][1005];

int main() {
    // Toi uu toc do nhap xuat
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int m, n;
    cin >> m >> n;

    long long tong = 0; // Bien luu tong cac so am

    // Nhap va xu ly voi chi so bat dau tu 1
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];

            // Kiem tra neu la so am thi cong vao tong
            if (a[i][j] < 0) {
                tong += a[i][j];
            }
        }
    }

    // In ra tong cac so am
    cout << tong;

    return 0;
}

5. Ví dụ mô phỏng

Input:

4 6
1 6 2 4 -7 10
6 3 -9 7 2 3
-6 5 0 1 1 -4
0 2 77 1 99 3

Các số âm trong bảng:

• Dòng 1: -7
• Dòng 2: -9
• Dòng 3: -6, -4
• Dòng 4: Không có số âm nào

Tính toán:

~tong = (-7) + (-9) + (-6) + (-4) = -26~

Output:

-26