Editorial for scbn1: Số cặp bằng nhau 1

Hiểu bài toán

Bài toán yêu cầu đếm số lượng các cặp phần tử liên tiếp trong dãy có giá trị bằng nhau. Cụ thể, với dãy số gồm n phần tử, ta cần đếm số chỉ số i (0 ≤ i ≤ n-2) sao cho a[i] == a[i+1]. Ví dụ: với dãy [4, 1, 1, 2, 2], ta có hai cặp (1,1) và (2,2) nên kết quả là 2.

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

Cách Duyệt đơn giản

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    int count = 0;
    for (int i = 0; i < n - 1; i++) {
        if (a[i] == a[i + 1]) {
            count++;
        }
    }
    printf("%d", count);
    return 0;
}

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

Đọc toàn bộ dãy số vào mảng, sau đó duyệt từ đầu đến phần tử áp chót, so sánh từng phần tử với phần tử tiếp theo. Nếu bằng nhau thì tăng biến đếm. Đây là cách tiếp cận trực quan nhất.

Cách Tối ưu bộ nhớ

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    if (n <= 1) {
        printf("0");
        return 0;
    }
    long long prev, curr;
    scanf("%lld", &prev);
    int count = 0;
    for (int i = 1; i < n; i++) {
        scanf("%lld", &curr);
        if (curr == prev) {
            count++;
        }
        prev = curr;
    }
    printf("%d", count);
    return 0;
}

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

Thay vì lưu toàn bộ dãy, ta chỉ cần lưu giá trị trước đó và giá trị hiện tại. Đọc từng phần tử, so sánh với giá trị trước đó, sau đó cập nhật biến lưu giá trị trước. Tiết kiệm bộ nhớ đáng kể với n lớn.

Cách Xử lý số lớn

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    long long prev, curr;
    int count = 0;
    if (n > 0) {
        scanf("%lld", &prev);
        for (int i = 1; i < n; i++) {
            scanf("%lld", &curr);
            if (curr == prev) count++;
            prev = curr;
        }
    }
    printf("%d", count);
    return 0;
}

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

Đảm bảo xử lý đúng giá trị lớn (sử dụng long long) và trường hợp n=0, n=1. Giữ logic tương tự cách tối ưu bộ nhớ nhưng chú ý xử lý biên.

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

Bài học kinh nghiệm

• Bài toán có thể giải quyết trong một lần duyệt duy nhất O(n)
• Không cần lưu toàn bộ dãy, chỉ cần theo dõi giá trị trước đó
• Đếm số cặp liên tiếp tương đương với đếm số vị trí i sao cho a[i] == a[i+1]

Lỗi thường gặp

• Quên kiểm tra n ≤ 1 (không có cặp)
• Dùng int để lưu giá trị có thể tràn số nếu a_i lên đến 10^9
• Lỗi chỉ số mảng khi duyệt: phải dừng ở n-2 hoặc so sánh i và i+1 với i < n-1