Hiểu bài toán

Bài toán mô phỏng việc Nam di chuyển sang trái hoặc sang phải dựa trên hiệu lệnh của giáo viên. Yêu cầu tính khoảng cách từ vị trí ban đầu sau khi thực hiện n lần di chuyển. Nếu hiệu lệnh là 1, Nam bước sang trái 1 mét (giảm tọa độ). Nếu là 2, Nam bước sang phải 1 mét (tăng tọa độ). Khoảng cách cần tính là giá trị tuyệt đối của tọa độ cuối cùng so với vị trí ban đầu (0).

Các cách tiếp cận

Cách Đếm số lượng hiệu lệnh

#include <iostream>
using namespace std;
int a[10000001];
int main(){
  long long n; cin >> n;
  int cnt1 = 0, cnt2 = 0;
  for (int i = 0; i < n; i++){
    cin >> a[i];
    if (a[i] == 1) cnt1++;
    else if (a[i] == 2) cnt2++;
  }
  cout << abs(cnt1 - cnt2);
  return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Phương pháp này đếm số lượng bước sang trái (1) và sang phải (2). Khoảng cách cuối cùng bằng hiệu số tuyệt đối giữa số bước trái và phải. Cách này sử dụng mảng để lưu các giá trị nhập vào, sau đó mới đếm, dẫn đến việc占用 bộ nhớ không cần thiết O(n) dù có thể giải quyết bài toán với O(1) bộ nhớ.

Cách Tính toán trực tiếp (Duyệt một lần)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    int res = 0;
    while (n--){
        int t; cin >> t;
        if(t == 1) res -= 1;
        else res += 1;
    }
    cout << abs(res);
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Đây là cách tiếp cận tối ưu nhất. Thay vì lưu trữ dữ liệu, ta dùng một biến res để theo dõi tọa độ hiện tại (hoặc chênh lệch giữa số bước trái/phải). Với mỗi hiệu lệnh, ta cập nhật trực tiếp res. Sau cùng, in ra giá trị tuyệt đối của res. Phương pháp này sử dụng bộ nhớ cố định và chỉ cần duyệt qua dữ liệu một lần.

Cách Sử dụng thư viện chuẩn C (scanf/printf)

#include <stdio.h>
#include <math.h>
int main(){
    int n;
    scanf("%d", &n);
    int i;
    int nam = 0;
    for(i = 0; i < n; i ++){
        int x;
        scanf("%d", &x);
        if(x == 1){
            nam -= 1;
        }
        else if(x == 2){
            nam += 1;
        }
    }
    printf("%d", abs(nam));
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Tương tự cách tiếp cận thứ hai, cách này sử dụng thư viện chuẩn C (stdio) để nhập/xuất. Logic tính toán giống hệt: dùng biến nam làm biến tích lũy, cộng trừ 1 đơn vị tùy vào hiệu lệnh. Kết quả cuối cùng là giá trị tuyệt đối của biến tích lũy.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể biến đổi thành bài toán tìm hiệu số giữa số lần sang trái và sang phải.
• Sử dụng biến tích lũy (running variable) để tính toán trong quá trình nhập dữ liệu giúp tiết kiệm bộ nhớ (O(1))

Lỗi thường gặp

• Quên lấy giá trị tuyệt đối của kết quả cuối cùng (ví dụ: nếu chỉ toàn sang trái, res âm).
• Sử dụng mảng cỡ lớn để lưu trữ đầu vào khi không cần thiết, gây tốn bộ nhớ.